Вопрос из интервью: Почему индекс MySQL использует дерево B+?

MySQL

предисловие

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

Структура индекса очень важна для производительности программы. Если индексов слишком мало, это повлияет на производительность запросов, если индексов слишком много, это повлияет на производительность добавления/изменения/удаления.

Точка знаний

MySQL обычно поддерживает следующие общие индексы:

  • Индекс дерева B+
  • полный текстовый указатель
  • хэш-индекс

Сегодня мы сосредоточимся на индексе дерева B+ и на том, почему мы используем дерево B+ в качестве структуры данных индекса.

Индекс дерева B+ не может напрямую найти конкретную строку, а только находит страницу, на которой находится искомая строка, а затем БД считывает всю страницу в память, а затем выполняет поиск в памяти.

Пересмотр структур данных

1.1 Структура хеша

Если есть 8 данных, таких как 3, 1, 2, 10, 9, 0, 4 и 6, создайте такие как图1-1Показан хэш-индекс.

  • прямой запрос: Теперь, чтобы найти запись 6 из 8 чисел, вам нужно только вычислить хэш-значение 6, чтобы быстро найти запись, а временная сложность составляет O (1).

  • запрос диапазона: Если вы хотите выполнять запросы диапазона (данные больше 4), то этот индекс совершенно бесполезен.

Рисунок 1-1 Хэш-индекс

1.2 Дерево поиска бинарного дерева

Двоичное дерево — это классическая структура данных, которая требует, чтобы левое поддерево было меньше корневого узла, а правое поддерево — больше корневого узла.

Если есть 8 данных, таких как 3, 1, 2, 10, 9, 0, 4 и 6, создайте такие как图1-2Показывается бинарное дерево поиска.

  • прямой запрос: Предполагая найти запись со значением ключа 6, сначала найдите корень 4, 4

  • запрос диапазона: если вам нужно найти данные больше 4, просто пройдите по правому поддереву 4.

Рисунок 1-2 Двоичное дерево поиска

1.3 Сбалансированное двоичное дерево (дерево AVL)

Согласно определению бинарного дерева поиска, его можно строить произвольно, одни и те же числа можно строить по图1-3-1способ построения бинарного дерева поиска. Аналогично, чтобы найти данные 6, нужно найти 5 раз.

Рисунок 1-3-1 Двоичное дерево поиска с низкой производительностью

Следовательно, чтобы построить бинарное дерево поиска с максимальной производительностью, его необходимо сбалансировать, то есть сбалансированное бинарное дерево.

Определение сбалансированного бинарного дерева: во-первых, оно соответствует определению бинарного дерева поиска, а максимальная разница между высотами двух поддеревьев любого узла равна 1.

Скорость запроса сбалансированного бинарного дерева очень высока, но у него есть недостатки:

  1. Стоимость обслуживания дерева очень велика, и при вставке или обновлении часто необходимо несколько раз повернуть влево или вправо, чтобы сохранить баланс. как图1-3-2показано
  2. Когда объем данных велик, дерево будет очень высоким, что потребует нескольких операций ввода-вывода.
  3. При выполнении поиска по диапазону, предполагая, что поиск >= 3, сначала будет найдено 3, затем необходимо найти родительский узел 3, а затем будет пройдено правое поддерево родительского узла.

Рисунок 1-3-2 Сбалансированное бинарное дерево AVL

1,4 Б+ дерево

В дереве B+ все узлы записей хранятся на листовых узлах иПоследовательное хранение, связанные указателями конечных узлов. Если начать последовательный обход с крайнего левого листового узла, можно получить порядок всех значений ключа.

Если восемь данных 3,1,2,10,9,0,4,6 могут создать сильно 1-4-1, показанное на фиг.2, представляет собой дерево B+.

РИС. 1-4-1 высота B + дерево 2

При обновлении дерева B+ также требуется операция вращения, аналогичная двоичному дереву. Например, если добавить 7, его можно заполнить непосредственно после 4 и 6. Если вы добавите еще 8, то вам нужно повернуть, почувствовать следующий процесс вращения дерева B+.

Рисунок 1-4-2 Дерево B+ высотой 3

Преимущества использования структуры индекса дерева B+:

  1. Высота дерева B+ обычно составляет 2-4 слоя, поэтому при поиске записей требуется максимум 2-4 IO, что значительно уменьшено по сравнению с бинарным сбалансированным деревом.
  2. При поиске по диапазону данные можно получить через указатель листового узла. Например, при поиске данных, больших или равных 3, когда 3 находится в листовом узле, все данные могут быть получены через хвостовой указатель 3, и нет необходимости снова получать родительский узел 3, как бинарное дерево.

Продолжение следует…

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

Категории