Обзор
Чтобы четко описать дерево B+, вы должны сначала понять число бинарного поиска и сбалансировать бинарное дерево.
бинарное дерево поиска
Для любого узла, если его левое поддерево не пусто, то значение всех узлов левого поддерева меньше значения корневого узла;
Для любого узла, если его правое поддерево не пусто, то значение всех узлов в правом поддереве больше, чем значение корневого узла.
Эта функция обеспечивает удобство поиска.Как показано на рисунке выше, чтобы найти значение ключа key=3, достаточно выполнить рекурсивный поиск из левого поддерева узла 6, а узлы в правом поддереве можно полностью игнорировать. .
Сбалансированное бинарное дерево
У бинарного дерева поиска есть некоторые недостатки, так как оно не имеет ограничений на высоту левого и правого поддеревьев дерева, в крайних случаях будет появляться связанный список, как на следующем рисунке:
Это бинарное дерево поиска не годится для запросов. Поэтому необходимо ограничивать высоту левого и правого поддеревьев узла дерева и стараться соблюдать баланс.
Двоичное сбалансированное дерево Рисунок 1
Двоичное дерево поиска Рисунок 2
Бинарное сбалансированное дерево требует, чтобы высота левого и правого поддеревьев узла не отличалась более чем на 1. Например, высота узла 6 на рис. 2, высота его левого поддерева равна 4, а высота правого поддерева равно 2. Разница превышает 1. Оно имеет характеристики сбалансированного бинарного дерева.
Из характеристик бинарного сбалансированного дерева видно, что эффективность запроса также очень высока, и в то же время он позволяет избежать экстремальной ситуации связанного списка в бинарном дереве поиска.
В+ дерево
Рисунок 3
Дерево B+ имеет несколько характеристик:
1. Это мультифорк вместо бинарного Цель использования мультифорка — уменьшить высоту дерева;
2. Каждый узел больше не хранит только один ключ, а может хранить несколько ключей;
3. Нелистовые узлы хранят ключи, а листовые узлы хранят ключи и данные.
4. Листовые узлы соединены парами, что помогает при последовательном запросе.
Почему Mysql выбирает дерево B+
1. Нелистовые узлы дерева B+ хранят только ключи и занимают очень мало места, поэтому диапазон данных, которые могут быть проиндексированы узлами на каждом уровне, шире. Другими словами, каждая операция ввода-вывода может просматривать больше данных;
2. Листовые узлы соединены парами, что соответствует функции упреждающего чтения диска. Как показано на рисунке 3, сохраняются листовые узлы 50 и 55. Он имеет указатель на листовые узлы 60 и 62. Когда мы читаем данные, соответствующие 50 и 55 с диска, благодаря функции предварительного чтения диска, это будет кстати.Прочитать данные соответствующие 60 и 62. В настоящее время это относится к последовательному чтению, а не к поиску по диску, что увеличивает скорость.
3. Запросы диапазона поддерживаются, и некоторые запросы диапазона очень эффективны. Причина в том, что данные хранятся в слое листовых узлов, и есть указатели на другие конечные узлы. Таким образом, запросам диапазона нужно только пройти через слой листовых узлов, без необходимости обхода всего дерева.
Краткое описание индекса Mysql
механизм хранения innodb
Автоинкрементный индекс первичного ключа
Самоувеличивающийся индекс первичного ключа использует дерево B+, а файл индекса также является файлом данных.данные для всей таблицы. То есть, когда мы выполняем sql-запрос по первичному ключу, нам нужно получить данные только из этого индексного файла. Этот тип индекса также называется кластерным индексом, поскольку все данные группируются в соответствии с первичным ключом.
Вспомогательный индекс (несамоувеличивающийся индекс первичного ключа, также называемый некластеризованным индексом)
Листовые узлы этого индексного файла хранят ключи и закладки. Значением ключа является значение столбца, а закладкой — значение первичного ключа соответствующей записи.Если данные запрашиваются по вспомогательному индексу, если покрывающий индекс не используется, то оценка составляет два шага :
1. Сначала получить первичный ключ, соответствующий данным из файла вспомогательного индекса;
2. Получить реальные данные из кластеризованного индекса по первичному ключу.
Механизм хранения MyISAM
Механизм MyISAM использует B+Tree в качестве структуры индекса, а поле данных конечного узла хранит адрес записи данных. Это называется некластеризованным индексом, который на самом деле является именем, соответствующим указанному выше innodb.
Оригинальная ссылка