Почему индекс MySQL реализован с деревом B+?

задняя часть база данных MySQL SQL
предисловие

При поиске определенных данных из кучи данных наши обычно используемые структуры данных представляют собой хеш-таблицы и двоичные деревья поиска.Таблица по сути представляет собой набор данных, поэтому база данных MySQL использует дерево B+ и хэш-таблицу для достижения индекса

Дерево B+ образовано из бинарного дерева поиска, сбалансированного бинарного дерева и дерева B (также известного как B-дерево). самое раннее сбалансированное бинарное дерево, но дерево B+ не является бинарным деревом

Бинарное дерево поиска и сбалансированное бинарное дерево

Эффективность бинарного дерева поиска и эффективность поиска сбалансированного бинарного дерева уже очень высоки, почему бы не использовать эти две структуры данных для реализации индекса? Не торопитесь анализировать

Бинарное дерево поиска — это бинарное дерево со специальными свойствами, которые должны удовлетворять следующим свойствам.

  1. Нелистовые узлы имеют не более двух дочерних узлов.

  2. Значение нелистового узла больше, чем у левого дочернего узла, и меньше, чем у правого дочернего узла.

  3. ни один узел с одинаковым значением не повторяется;

Найдите двоичное дерево на рисунке выше.Например, чтобы найти запись со значением ключа 5, сначала найдите корень со значением 6, которое больше 5, найдите левое поддерево 6, найдите 3, 5 больше 3, а затем найти его правое поддерево, всего поиск выполняется 3 раза. Таким же образом требуется 3 раза найти запись со значением ключа 8. Среднее количество поисков всех значений ключа равно (1+2+2+3+3+3)/6=2,3 раза.Если эти значения ключа искать последовательно, среднее количество поисков равно (1+ 2+3+4+5+ 6)/6=3,3 (числа расположены в порядке поиска, первое число должно быть 1 раз, второе число 2 раза и т. д.), очевидно, средняя скорость поиска двоичного дерево поиска быстрее, чем последовательный поиск.

Бинарное дерево поиска может быть построено произвольно, если бинарное дерево поиска построено следующим образом.

Средняя скорость поиска составляет (1+2+3+4+5+5)/6=3,16 раза, что аналогично последовательному поиску. Чтобы повысить эффективность запроса двоичного дерева поиска, необходимо сбалансировать количество двоичных поисков, что приводит к сбалансированному двоичному дереву.

В дополнение к удовлетворению трех вышеуказанных свойств сбалансированное бинарное дерево также должно удовлетворять следующему свойству:

  1. Количество уровней в левой и правой частях дерева не будет отличаться более чем на 1

Эффективность поиска сбалансированного бинарного дерева действительно очень высока, но стоимость поддержания сбалансированного бинарного дерева очень высока, и требуется одно или несколько левых и правых вращений, чтобы получить баланс дерева после вставки или Обновить. Просто приведите пример.

Изначально сбалансированное бинарное дерево

Вставка 3

повернуть направо один раз

снова повернуть налево

В качестве научно-популярной статьи я не буду разбирать здесь детали леворукости и праворукости.Поместите несколько картинок для понимания леворукости и праворукости.

Левосторонний x означает превращение x в левый узел

Поверните y вправо, что означает превращение y в правый узел

Оглядываясь назад на левое и правое вращение в приведенном выше примере, ясно ли это?

B-деревья и B+ деревья

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

Хотя эффективность поиска сбалансированного бинарного дерева действительно очень высока, узким местом, мешающим повышению производительности, является частый ввод-вывод.Как уменьшить количество операций ввода-вывода? Предшественники очень умно предложили принцип локальности, который делится на принцип локальности времени, то есть, если вы запрашиваете пользовательские данные с идентификатором 1, вы также будете запрашивать данные с идентификатором 1 через определенный период времени, поэтому эта часть данных будет кэширована. В соответствии с принципом пространственной локальности, когда вы запрашиваете данные пользователя с идентификатором 1, у вас есть высокая вероятность запросить данные пользователя с идентификатором 2, 3 и 4, поэтому идентификатор равен 1, 2. , Данные 3 и 4 считываются в память, а самой маленькой единицей является страница.

Понятия B-tree и B+дерева более сложны.Заинтересованные друзья могут нажать на оригинальную ссылку, чтобы увидеть статью, написанную на Zhihu.Здесь только введение в макрос.Как упоминалось выше, высота дерева определяет количество IO.Итак неужели уменьшение высоты дерева не может уменьшить количество IO?Как его уменьшить?Достаточно поставить больше данных на каждую ноду,и эти данные хранятся в одном блоке,что соответствует минимальной единичной странице считанной в БД. , данные могут быть считаны за один ввод-вывод.Хотя количество сравнений может увеличиться, сравнение в памяти на несколько порядков хуже, чем при дисковом вводе-выводе, а общая эффективность все равно повышается.

Итак, B-дерево, которое вы видите, выглядит так

В+ дерево такое

Так в чем же разница между деревом B и деревом B+?

  1. B+ отличается от дерева B. Неконечные узлы дерева B+ не сохраняют данные, соответствующие значению ключа, что значительно увеличивает значение ключа, которое может сохранить каждый узел дерева B+;

  2. Листовой узел B+ сохраняет все значения ключа родительского узла и данные, соответствующие значению ключа, а значение ключа каждого конечного узла связывается от малого к большому;

  3. Количество ключевых значений корневого узла дерева B+ равно количеству его дочерних узлов;

  4. Нелистовые узлы B+ выполняют только индексирование данных и не хранят данные, соответствующие фактическому значению ключа.Все данные должны быть получены из конечных узлов, поэтому количество запросов данных каждый раз одинаково;

Поместите картинку, чтобы понять более четко, B дерево

В+ дерево

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

Кластерные и федеративные индексы

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

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

  2. Если вышеуказанные условия не выполняются, механизм хранения InnoDB автоматически создает 6-байтовый указатель в качестве индекса.

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

Если есть следующие данные, идентификатор пользователя является первичным ключом (1, tom), (2, mike), (3, sam), (4, lisa), (5, li), тогда данные сохраняются как это, рисунок 1

Предположим, теперь мы строим индекс имени пользователя. Как существует индекс имени пользователя? фигура 2

Данные конечного узла индекса имени пользователя хранят первичный ключ, поэтому, когда мы запускаем следующую инструкцию sql

select * from table where name ="sam"скопировать код

Процесс такой, сначала найти соответствующий первичный ключ по индексу имени, а затем найти соответствующую запись в дереве B+, установленном при построении таблицы по соответствующему первичному ключу, то есть сначала найти его на рисунке 1, а затем найти его на рисунке 2.

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

Некластеризованный индекс: Определение: Логический порядок индекса в этом индексе отличается от физического порядка хранения строки диска, и таблица может иметь несколько некластеризованных индексов. На рисунке 2 используется некластеризованный индекс.

Наконец, давайте поговорим о совместном индексе.Совместный индекс относится к индексации нескольких столбцов в таблице. Создано следующим образом:

CREATE TABLE `t` (  `a` int(10),  `b` int(10),  PRIMARY KEY (`a`),  KEY `idx_a_b` (`a`,`b`)) ENGINE=InnoDB;скопировать код

Совместный индекс также является деревом B+.Разница в том, что количество ключевых значений объединенного индекса не равно 1, а больше или равно 2. Дерево B+ множественных значений ключа хранится следующим образом

Вы можете видеть, что значения ключей отсортированы, в приведенном выше примере (1, 1) (1, 2) (2, 1) (2, 4) (3, 1) (3, 2) данные в соответствии с (а, б) хранятся в порядке.

Следовательно, для запроса выберите * из таблицы, где a = xxx и b = xxx, очевидно, что можно использовать совместный индекс (a, b). Для одного столбца запрос выбирает * из таблицы, где a = xxx, также может использоваться индекс (a, b). Но для запроса выберите * из таблицы, где b = xxx для столбца b, этот индекс дерева B+ нельзя использовать. Можно обнаружить, что значение b на листовом узле равно 1, 2, 1, 4, 1, 2, что, очевидно, не отсортировано, поэтому запрос столбца b не может использовать индекс (a, b)

Адаптивный хэш-индекс

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

В базе данных обычно используется метод деления и хеширования, то есть берется остаток от деления k на m и сопоставляется ключевое слово k с одним из m слотов, то есть хэш-функция имеет вид h(k) = k mod m , когда возникает конфликт, то есть два ключевых слова могут быть сопоставлены с одним и тем же слотом, и используется метод ссылки, то есть конфликтующие ключевые слова сохраняются в виде связанного списка, аналогичного HashMap

После того, как хэш-индекс установлен для горячих данных, поиск по дереву B+ опускается, что может значительно повысить производительность службы.Адаптивный хэш-индекс очень быстр для поиска типов словарей, таких как выбор * из таблицы где id=xxx, но для поиска по диапазону это бессильно

Категории