Использование Postgres индексов btree против MySQL B + деревьев

Мы находимся в процессе перехода от MySQL к PGSQL, и у нас есть таблица из 100 миллионов строк.

Когда я пытался выяснить, сколько места используют обе системы, я нашел гораздо меньше различий для таблиц, но нашел огромные различия для индексов.

Индексы MySQL занимали больше размера, чем сами данные таблицы, а postgres использовали значительно меньшие размеры.

При переходе по этой причине я обнаружил, что MySQL использует деревья B + для хранения индексов и postgres использует B-деревья.
Использование индексов MySQL было немного иным, оно хранит данные вместе с индексами (из-за которых увеличивается размер), но postgres этого не делает.

Теперь вопросы:

Сравнение B-tree и B + деревьев в базе данных говорит, лучше использовать деревья B +, так как они лучше подходят для запросов диапазона O (m) + O (logN) - где m в диапазоне и поиске логарифмически в деревьях B +?

Теперь в B-деревьях поиск является логарифмическим для запросов диапазона, которые он снимает до O (N), так как он не имеет связанной структуры списка для узлов данных. С учетом сказанного, почему postgres использует B-деревья? Он хорошо работает для запросов диапазона (он делает, но как он обрабатывает внутренне с B-деревьями)?
Вышеупомянутый вопрос с точки зрения postgres, но с точки зрения MySQL, почему он использует больше хранилища, чем postgres, какова эффективность использования деревьев B + в действительности?

Я мог бы пропустить/неправильно понять многие вещи, поэтому, пожалуйста, не стесняйтесь исправить мое понимание здесь.

Изменить для ответа на вопросы Рика Джеймса

Я использую движок InnoDB для MySQL
Я построил индекс после заполнения данных - так же, как в postgres
Индексы не являются УНИКАЛЬНЫМИ индексами, просто нормальными индексами
Не было случайных вставок, я использовал загрузку csv как в postgres, так и в MySQL, и только после этого я создал индексы.
Размер блока Postgres для индексов и данных составляет 8 КБ, я не уверен в MySQL, но я не изменил его, поэтому он должен быть по умолчанию.
Я бы не назвал строки большими, у них было около 4 текстовых полей длиной 200 символов, 4 десятичных поля и 2 поля bigint - 19 чисел.
P.K - это столбец bigint с 19 номерами, я не уверен, что это громоздко? В каком масштабе следует дифференцировать объемные и непрозрачные?
Размер таблицы MySQL составлял 600 МБ, а Postgres - около 310 МБ, включая индексы - это составляет 48% большего размера, если моя математика права. Но есть ли способ, чтобы я мог измерять только размер индекса в MySQL, исключая размер стола? Это может привести к лучшим числам, которые я предполагаю.
Информация о машине: у меня было достаточно ОЗУ - 256 ГБ, чтобы объединить все таблицы и индексы, но я не думаю, что нам нужно пройти этот маршрут вообще, я не видел заметной разницы в производительности в обоих из них.

Дополнительные вопросы

Когда мы говорим, что происходит фрагментация? Есть ли способ сделать де-фрагментацию, чтобы мы могли сказать, что помимо этого ничего не поделаешь. Я использую Cent OS, кстати.
Есть ли способ измерения размера индекса в MySQL, игнорируя первичный ключ, поскольку он кластерный, так что мы действительно можем видеть, какой тип занимает больше размера, если таковой имеется.

Ответ 1

Прежде всего, если вы не используете InnoDB, закройте этот вопрос, перестройте с помощью InnoDB, а затем посмотрите, нужно ли повторно открыть вопрос. MyISAM не является предпочтительным и не должен обсуждаться.

Как вы построили индексы в MySQL? Существует несколько способов явно или неявно создавать индексы; они приводят к лучшей или худшей упаковке.

MySQL: данные и индексы хранятся в B + деревьях, состоящих из блоков 16 КБ.

MySQL: UNIQUE индексы (включая PRIMARY KEY) должны быть обновлены при вставке строк. Таким образом, индекс UNIQUE обязательно будет иметь много разбиений блоков и т.д.

MySQL: PRIMARY KEY с кластеризацией с данными, поэтому он эффективно занимает нулевое пространство. Если вы загружаете данные в порядке PK, то фрагментация блока минимальна.

Не-UNIQUE вторичные ключи могут быть созданы на лету, что приводит к некоторой фрагментации. Или они могут быть построены после загрузки таблицы; это приводит к более плотной упаковке.

Вторичные ключи (UNIQUE или не) неявно включают в них PRIMARY KEY. Если PK "большой", то вторичные ключи являются громоздкими. Что такое ваш ПК? Это "ответ"?

Теоретически, полностью случайные вставки в БТРИ приводят к тому, что блоки составляют 69% полных. Может быть, это и есть ответ. Является ли MySQL на 45% больше (1/69%)?

С 100-миллиметровыми строками, вероятно, многие операции связаны с I/O-привязкой, потому что у вас недостаточно ОЗУ для кэширования всех необходимых данных и/или блоков индексов. Если все кэшируется, то B-Tree против B + Tree не будет иметь большого значения. Проанализируйте, что должно произойти для запроса диапазона, когда вещи не полностью кэшируются.

В любом типе дерева операция начинается с разворота в дереве. Для MySQL строки 100M будут иметь дерево B +, состоящее примерно из 4 уровней. 3 нелистовых узла (еще 16 КБ блоков) будут кэшироваться (если они еще не были) и будут повторно использоваться. Даже для Postgres это кеширование, вероятно, происходит. (Я не знаю Postgres.) Затем начинается сканирование диапазона. С MySQL он проходит через остальную часть блока. (Правило большого пальца: 100 строк в блоке.) То же для Postgres?

В конце блока должно произойти что-то другое. Для MySQL есть ссылка на следующий блок. Этот блок (со 100 строками) извлекается с диска (если не кэшируется). Для B-дерева снова необходимо пересечь нелистовые узлы. 2, вероятно, 3 уровня все еще кэшируются. Я ожидал бы, что еще один не-лист node будет извлечен с диска только с 1/10K строк. (10K = 100 * 100) То есть Postgres может поражать диск на 1% чаще, чем MySQL, даже в "холодной" системе.

С другой стороны, если строки настолько толстые, что только 1 или 2 могут поместиться в блок 16K, то "100", которые я использовал, больше напоминает "2", а 1% составляет, возможно, 50%. То есть , если у вас большие строки, это может быть "ответ" . Это?

Каков размер блока в Postgres? Обратите внимание, что многие из вышеперечисленных вычислений зависят от относительного размера между блоком и данными. Это может быть ответ?

Вывод: Я дал вам 4 возможных ответа. Хотелось бы увеличить вопрос, чтобы подтвердить или опровергнуть, что каждый из них применяется? (Наличие вторичных индексов, больших ПК, неэффективное построение вторичных индексов, больших строк, размер блока,...)

Дополнения к PRIMARY KEY

Для InnoDB, еще одно замечание... Лучше всего иметь PRIMARY KEY в определении таблицы перед загрузкой данных. Также лучше сортировать данные в порядке PK до LOAD DATA. Без указания клавиши PRIMARY KEY или UNIQUE InnoDB создает скрытую 6-байтную PK; это обычно неоптимально.

Ответ 2

В базах данных у вас часто возникают запросы, которые предоставляют некоторые диапазоны данных, такие как id от 100 до 200.
В этом случае

B-Tree должен следовать по пути от корня до листьев для каждой отдельной записи, чтобы получить указатель данных.
B + -Trees могут "ходить" по листьям и должны следовать по пути к листьям только в первый раз (то есть для идентификатора 100)

Это связано с тем, что B + -Trees хранит только данные (или указатель данных) в листах, а листы связаны так, что вы можете выполнить быстрый обход в порядке.

В + -Tree

Еще один момент:
В B + Trees внутренние узлы сохраняют только указатель на другие узлы без какого-либо указателя данных, поэтому у вас больше места для указателей, и вам нужно меньше операций ввода-вывода, и вы можете хранить больше node -потоков на странице памяти.

Таким образом, для запросов диапазона B + -Trees являются оптимальной структурой данных. Для одиночных выборов B-Trees может быть лучше (причины глубины/размера дерева), заставляют указатель данных также находиться внутри дерева.

Ответ 3

MySQL и PostgreSQL на самом деле не сравнимы здесь. Innodb использует индекс для хранения данных таблицы (а вторичные индексы просто указывают на pkey). Это отлично подходит для однострочных поисков pkey и с деревьями B +, все в порядке с запросами диапазона в поле pkey, но имеет недостатки производительности для всего остального.

PostgreSQL использует таблицы кучи и ставит индексы как отдельные. Он поддерживает ряд различных алгоритмов индексирования. В зависимости от вашего запроса диапазона, индекс btree может вам не помочь, и вам может понадобиться индекс GiST. Аналогично, индексы GIN хорошо работают с элементами поиска (для массивов, fts и т.д.).

Я думаю, что btree используется, потому что он превосходит в простом случае: какие кошельки содержат следующие данные? Это становится, например, строительным блоком GIN.

Но это не так, что PostgreSQL не может использовать деревья B+. GiST построен на индексах B + Tree в обобщенном формате. Таким образом, PostgreSQL дает вам возможность использовать деревья B +, где они пригождаются.