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

Question

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

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

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

• При рытье через по той причине, я обнаружил, что MySQL использует B + деревьев для хранения индексов и Postgres uses B-деревьев.

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

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

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

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

• Этот вопрос относится с точки зрения postgres, но с точки зрения MySQL, почему он использует больше хранилища, чем postgres, какова эффективность использования деревьев B + в действительности?

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

Edit для ответа Рик Джеймс расспрашивает

• Я использую InnoDB двигатель для MySQL
• Я построил индекс после заполнения данных - так же я сделал в Postgres
• Индексы не являются UNIQUE индексы, только нормальные индексы
• Не было случайных вставок, я использовал загрузку 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, игнорируя первичный ключ, поскольку он является кластеризованным, так что мы действительно можем видеть, какой тип занимает больше размера, если таковой имеется.

Answer 1

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

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

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

B + -Tree

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

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

Answer 2

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

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

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

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

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

Non-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 уровня все еще кэшируются. Я ожидал бы, что другой нелистовой узел будет извлекаться с диска только с 1/10K строк. (10K = 100 * 100) То есть Postgres может поражать диск на 1% чаще, чем MySQL, даже в «холодной» системе.

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

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

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

Addenda о PRIMARY KEY

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

Answer 3

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

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

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

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