Нижний слой индекса MySQL: подробное объяснение дерева B+

предисловие

Когда мы обнаруживаем, что выполнение SQL очень медленное, мы, естественно, думаем о добавлении индексов. Для запросов диапазона базовой структурой индекса является дерево B+. Сегодня давайте вместе узнаем о дереве B+~

публика:маленький мальчик собирает улиток

• Знакомство с деревьями, виды деревьев

• Введение в B-дерево и B+ дерево

• Вставка дерева B+

• B+ поиск по дереву

• Удаление дерева B+

• Классические вопросы для собеседования B+

• адрес github, спасибо за каждую звезду

GitHub.com/Я бы хотел 123/Java…

Знакомство с деревом

Знакомство с деревом

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

Дерево — это конечное множество, содержащее n (n — целое число, большее 0) узлов и n-1 ребер и обладающее следующими характеристиками:

• Каждый узел либо не имеет дочерних узлов, либо имеет только ограниченное количество дочерних узлов;
• Есть конкретный узел, у него нет родительского узла, называемого корневым узлом;
• Каждый некорневой узел имеет один и только один родительский узел;
• В дереве нет петель

Некоторые понятия о деревьях:

• Степень узла: количество дочерних узлов, содержащихся в узле, называется степенью узла;
• Степень дерева: В дереве степень наибольшего узла называется степенью дерева;
• Родительский узел: если узел содержит дочерний узел, этот узел называется родительским узлом своего дочернего узла;
• Глубина: для любого узла n глубина n — это длина уникального пути от корня до n, а глубина корневого узла равна 0;
• Высота: для любого узла n высота n — это самый длинный путь от n до листа, а высота всех листьев равна 0;

Вид дерева

По порядку его можно разделить на упорядоченное дерево и неупорядоченное дерево:

• Неупорядоченное дерево: между дочерними элементами любого узла в дереве нет упорядоченных отношений.
• Упорядоченное дерево: существует отношение порядка между дочерними узлами любого узла в дереве.

По количеству поддеревьев, содержащихся в узле, его можно разделить на B-дерево и бинарное дерево.Двоичное дерево можно разделить на следующие типы:

• Двоичное дерево: дерево с не более чем двумя поддеревьями на узел называется бинарным деревом;
• Двоичное дерево поиска: Во-первых, это бинарное дерево, если левое поддерево не пусто, то значение всех узлов левого поддерева меньше значения его корневого узла, если правое поддерево не пусто, то правое поддерево Значение всех вышеперечисленных узлов больше значения его корневого узла, левое и правое поддеревья также являются деревьями с бинарной сортировкой;
• Полное бинарное дерево: дерево, в котором все узлы, кроме листовых, содержат два поддерева, называется полным бинарным деревом;
• Полное бинарное дерево: если бинарное дерево является полным бинарным деревом, за исключением последнего слоя узлов, а узлы последнего слоя распределяются слева направо по очереди.
• Дерево Хаффмана: бинарное дерево с кратчайшим взвешенным путем.
• Красно-черное дерево: Красно-черное дерево — это специальное бинарное дерево поиска, каждый узел которого черный или красный, а корневой узел и листовой узел — черные. Если узел красный, его потомки должны быть черными.
• Сбалансированное двоичное дерево (AVL): абсолютное значение разницы высот пустого дерева или его левого и правого поддеревьев не превышает 1, а левое и правое поддеревья являются сбалансированным двоичным деревом.

Введение в B-дерево и B+ дерево

Введение в B-деревья

B-дерево, также известное как B-дерево, представляет собой сбалансированное дерево с несколькими разветвлениями (в отличие от сбалансированного бинарного дерева поиска), которое больше подходит для внешнего поиска. Взгляните на эти понятия:

• Порядок: максимальное количество дочерних узлов у узла. (обычно обозначается буквой м)
• Ключевое слово: значение на узле является ключевым словом
• Степень: количество дочерних элементов узла.

B-дерево порядка m имеет следующие характеристики:

• Корневой узел имеет как минимум двух дочерних узлов;
• Количество ключевых слов j, содержащихся в каждом некорневом узле, удовлетворяет условию: ⌈m/2⌉ - 1
• Нелистовой узел с k ключами (ключевые слова в порядке возрастания) имеет ровно k+1 потомков.
• Все листовые узлы расположены на одном уровне.

Простое B-дерево выглядит следующим образом:

Введение в деревья B+

Дерево B+ — это вариант B-дерева, а также дерево многостороннего поиска. Дерево B+ порядка m в основном имеет следующие характеристики:

• Каждый узел имеет не более m потомков;
• Диапазон количества ключевых значений некорневых узлов: m/2
• Смежные листовые узлы соединены указателями и отсортированы по размеру ключа.

Дерево B+ порядка 3 выглядит следующим образом:

Основные отличия B+-дерева от B-дерева заключаются в следующем:

• Внутренние узлы B-дерева хранят данные, в то время как внутренние узлы B+ дерева не хранят данные, они используются только для индексации, а его конечные узлы хранят данные.
• Смежные листовые узлы B+-дерева соединены указателями связанных списков, а B-дерево — нет.
• В процессе поиска B-дерево заканчивается после нахождения определенного значения, в то время как B+-дереву необходимо найти данные в листовом узле по индексу до конца.
• Любое ключевое слово в B-дереве появляется и появляется только в одном узле, в то время как дерево B+ может появляться несколько раз.

Вставка дерева B+

Запомните эти шаги для вставки дерева B+:

• 1. Вставка B+-дерева выполняется в листовой узел, то есть перед вставкой необходимо найти вставляемый листовой узел.
• 2. Если количество ключевых слов, содержащихся в настоящее время в листовом узле вставленного ключевого слова, меньше порядка m, вставить его напрямую.
• 3. Если после вставки ключевого слова количество ключевых слов, содержащихся в данный момент в листовом узле, равно порядку m, то при вставке узел начинаетРасколотьДля двух новых узлов один узел содержит ⌊m/2⌋ ключевых слов, а другой — ⌈m/2⌉ ключевых значений. (⌊m/2⌋ означает округление в меньшую сторону, ⌈m/2⌉ означает округление в большую сторону, например, ⌈3/2⌉=2).
• 4. После разделения вам нужно переместить ключевое слово ⌈m/2⌉ на родительский узел. Если в этот момент количество ключевых слов, содержащихся в родительском узле, меньше m, операция вставки завершается.
• 5. После разделения ключевое слово ⌈m/2⌉ необходимо переместить на родительский узел. Если количество ключевых слов, содержащихся в родительском узле, равно m, продолжайте разбивать родительский узел.

В качестве примера возьмем дерево B+ 4-го порядка.Если это дерево 4-го порядка, существует не более 3 (m-1) значений ключа. Предположим, вставлены следующие данные: 43, 48, 36, 32, 37, 49, 28.

1. Вставьте 43 в пустое дерево

В это время корневой узел имеет ключевое значение, и в это время он является корневым узлом и конечным узлом.

2. Вставить 48, 36 по очереди

В это время в узле есть 3 ключевых слова, которые заполнены

3. Продолжайте вставлять 32 и обнаружите, что текущее ключевое слово узла имеет порядок не меньше 4, поэтому разделите

⌈4/2⌉=2 (индекс 0,1,2), то есть 43 перемещается вверх к родительскому узлу.

4. Продолжайте вставлять 37, 49, ключевые слова предыдущего узла не заполнены, вставьте напрямую, как показано ниже:

5. Наконец, вставьте 28 и обнаружите, что ключевое слово текущего узла имеет порядок не меньше 4, поэтому разделите первое ⌈4/2⌉=2, то есть 36 перемещается вверх к родительскому узлу, потому что родительский и дочерний узлы имеют только 2 значения ключа или менее 4, поэтому нет необходимости продолжать разбиение, вставка завершена

Вы можете взглянуть на динамическую картинку (она немного длинная, терпеливо подождите):

B+ поиск по дереву

Поскольку все данные дерева B+ находятся на листовых узлах, внутренний узел является только функцией индекса указателя, поэтому процессу поиска необходимо искать конечные узлы. Давайте возьмем это дерево B+ в качестве примера:

Запрос одного значения дерева B+

Предположим, что значение, которое мы хотим проверить, равно 32.

Для первого дискового ввода-вывода ищите дисковый блок 1, который является корневым узлом (36, 43), поскольку 32 меньше 36, поэтому обращайтесь к первому дочернему узлу слева от корневого узла.

Для второго дискового ввода-вывода найдите дисковый блок 2, который является первым дочерним узлом корневого узла, получите интервал (28,32) и пройдите, чтобы получить 32.

Динамическая диаграмма выглядит следующим образом:

Запрос диапазона дерева B+

Предположим, мы хотим найти значения в интервале [32,40].

Первый шаг — посетить корневой узел и обнаружить, что левая конечная точка 32 интервала меньше 36, затем посетить первое левое поддерево корневого узла (28,32);

Второй шаг — посетить узел (28, 32) и найти 32, поэтому начните обход связанного списка и найдите значение интервала [32, 40], где дерево B+ более эффективно, чем дерево B-. .

Удаление дерева B+

Ключевые слова удаления дерева B+, разделенные на эти ситуации

• Найдите узел, содержащий значение ключа, если количество ключевых слов больше m/2, просто удалите его напрямую;
• Найдите узел, содержащий значение ключа.Если количество ключевых слов больше, чем m/2, а значение ключа является максимальным (наименьшим) значением текущего узла, а значение ключа существует в родительском и дочернем узлах, удалите ключевое слово и откорректируйте его соответствующим образом. Значение родительского узла.
• Найдите узел, содержащий значение ключа, если после удаления ключевого слова количество ключевых слов меньше ⌈m/2⌉, а в родственном узле есть избыточные ключевые слова, заимствуйте ключевое слово из родственного узла
• Найдите узел, содержащий значение ключа, если количество ключевых слов меньше ⌈m/2⌉ после удаления ключевого слова, а его одноуровневые узлы не имеют избыточных ключевых слов, затем объедините их с одноуровневыми узлами.

Если количество ключевых слов превышает ⌈m/2⌉, просто удалите его напрямую;

Предположим, что существует такое B+-дерево 5-го порядка

Если вы удалите 22, поскольку количество ключевых слов 3 > 5/2 = 2, удалите его напрямую (⌈⌉ означает округление в большую сторону).

Если количество ключевых слов больше ⌈m/2⌉-1, а удаленное ключевое слово существует в родительском и дочернем узлах, то значения родительского и дочернего узлов необходимо соответствующим образом скорректировать.

Если вы удалите 20, поскольку количество ключевых слов 3 > 5/2=2, а 20 является граничным значением текущего узла, и он существует в родительском и дочернем узлах, после удаления его родительский и дочерний узлы также должны реагировать на регулировку.

Если после удаления ключевого слова количество ключевых слов меньше m/2, одноуровневые узлы могут заимствовать

Следующее дерево B+ 5-го порядка,

При удалении 15 в узле, где удалено ключевое слово, остается только 1 ключевое слово, что меньше 5/2=2, что не соответствует характеристикам дерева B+, но его родственный узел имеет 3 элемента (7, 8 , 9), а 9 можно заимствовать. , как показано на рисунке:

После удаления ключевого слова, если количество ключевых слов в узле недостаточно, а родственный узел не должен его заимствовать, родственный узел необходимо объединить

Следующее дерево B+ 5-го порядка:

При удалении ключевого слова 7 в узле, где удалено ключевое слово, остается только 1 ключевое слово, что меньше 5/2=2, что не удовлетворяет характеристикам дерева B+, а одноуровневые узлы не могут быть заимствованы, поэтому происходит слияние , следующее:

Основной процесс приготовления фиолетового соуса:

• Потому что после удаления 7 остается только одно ключевое слово из 8, которое не соответствует характеристикам дерева B+ (m/2
• И нет заимствования ключевых слов родственного брата, поэтому 8 сочетается с предыдущим братом.
• Родительский узел удаленного ключевого узла, индекс 7, также был удален, осталась только одна 9, а его правый родственный узел (18, 20) имеет только два ключевых слова, и его нельзя заимствовать, поэтому он здесь объединен.
• После того, как узел родитель-потомок удаленного узла ключевого слова также объединяется с его дочерним узлом, остается только одна ветвь поддерева, поэтому корневой узел (16) также перемещается вниз.

Таким образом, результат после удаления ключевого слова 7 выглядит следующим образом:

Классические вопросы для собеседования B+

• Сколько строк данных может хранить дерево B+ в InnoDB?
• Почему в структуре индекса по умолчанию используется дерево B+ вместо хэша, бинарного дерева, красно-черного дерева, B-дерева?
• Разница между B-деревом и B+ деревом

Сколько строк данных может хранить дерево B+ в InnoDB?

Простой ответ на этот вопрос: около 20 миллионов строк.

• В компьютере наименьшая единица хранения данных на диске — это сектор, а размер сектора — 512 байт.
• В файловой системе наименьшая единица — блок, а размер блока — 4 КБ;
• Минимальная единица хранения механизма хранения InnoDB — это страница, а размер страницы — 16 КБ.

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

Предполагая, что высота дерева B+ равна 2, имеется один корневой узел и несколько конечных узлов. Общее количество записей, хранящихся в этом дереве B+, равно количеству указателей на корневые узлы * количеству строк, записанных в одном листовом узле.

• Если размер данных строки записей равен 1 КБ, то количество записей, которые может хранить один конечный узел, = 16 КБ/1 КБ = 16.
• Сколько указателей хранится в нелистовых узлах? Мы предполагаем, что идентификатор первичного ключа имеет тип bigint, длина равна 8 байтам, а размер указателя установлен на 6 байтов в исходном коде InnoDB, поэтому он равен 8+6=14 байтам, 16k/14B = 16*1024B. /14В = 1170

Следовательно, дерево B+ высотой 2 может хранить 1170 * 16 = 18720 таких записей данных. Точно так же дерево B+ высотой 3 может хранить 1170 * 1170 * 16 = 21902400, то есть оно может хранить около 20 миллионов записей. Высота дерева B+ обычно составляет 1-3 слоя, что соответствует хранилищу данных в десятки миллионов.

Почему в структуре индекса по умолчанию используется дерево B+ вместо B-Tree, Hash, бинарного дерева, красно-черного дерева?

Простой ответ заключается в следующем:

• Хеш-хэш, подходит только для запроса равного значения, не подходит для запроса диапазона.
• Обычное двоичное дерево может быть специализировано как связанный список, что эквивалентно полному сканированию таблицы.
• Красно-черное дерево — это специализированное сбалансированное бинарное дерево.При большом количестве данных MySQL будет большим и объем индекса.Если память не может быть сохранена, она будет прочитана с диска.Если уровень дерево слишком высокое, данные будут считаны с диска.Больше раз.
• B-дерево, как листовые, так и нелистовые узлы хранят данные, одинаковое количество данных, дерево B+ предпочитает короткие и сильные, то есть одинаковое количество данных, структура данных дерева B+, количество запросов к диску будет быть меньше.

Разница между B-деревом и B+ деревом

• Внутренние узлы B-дерева хранят данные, в то время как внутренние узлы B+ дерева не хранят данные, они используются только для индексации, а его конечные узлы хранят данные.
• Смежные листовые узлы B+-дерева соединены указателями связанных списков, а B-дерево — нет.
• В процессе поиска B-дерево заканчивается после нахождения определенного значения, в то время как B+-дереву необходимо найти данные в листовом узле по индексу до конца.
• Любое ключевое слово в B-дереве появляется и появляется только в одном узле, в то время как дерево B+ может появляться несколько раз.

Ссылка и спасибо

• Дерева B+ достаточно, чтобы прочитать это
• Подробное объяснение вставки и удаления B-деревьев и B+-деревьев
• Сколько строк данных может хранить дерево B+ в InnoDB?