По мере увеличения размера таблиц в базе данных последовательная файловая организация начинает работать плохо с точки зрения поиска по индексу. Индекс деревьев B + является многоуровневым индексом, но отличается от последовательного файла многоуровневого индекса. «B» в B + деревьях означает слово «сбалансированный», которое действительно является свойством этих деревьев. В этой статье мы рассмотрим поиск, вставку и удаление в дереве B +.
Примеры в этой статье взяты из книги Концепции системы баз данных.
Структура B + деревьев
Узлы деревьев B + обычно содержат более двух указателей и из-за этого они короче простого двоичного дерева, которое имеет только два указателя, соответствующих одному узлу. На рисунке ниже показана структура узла дерева B +.
Здесь Kᵢ обозначает ключевые значения, а Pᵢ обозначает указатели, которые будут указывать на его дочерние элементы. Эти деревья чем-то похожи на деревья двоичного поиска (не полностью), поскольку указатель Pᵢ указывает на записи в базе данных, которые находятся между ключами K₍ᵢ₋₁₎ и Kᵢ. Каждый узел дерева B + может иметь не более «n» указателей (это n является свойством конкретного дерева). Каждый узел может содержать максимум n-1 ключей. Конечные узлы содержат минимум \ ceil {frac {n-1} {2} ключей, в то время как внутренний узел должен иметь как минимум \ ceil {{n} {2}} указатель. Указатели конечных узлов указывают на строки базы данных, как показано на рисунке.
Запросы в B + Tree
Предположим, у нас есть дерево B +, как показано на рисунке ниже.
Учитывая значение ключа K, нам нужно найти соответствующую ему строку. В каждом узле нам нужно найти наименьшее значение ключа, которое больше, чем K. Если Kᵢ - наименьший ключ, который больше, чем K, тогда мы перейдем к узлу, указанному Pᵢ. Если мы не можем найти такой указатель, мы должны перейти к узлу, на который указывает последний указатель. Мы будем следовать этому итеративному процессу, чтобы достичь листового узла. Если ключ iᵗʰ равен K, тогда Pᵢ укажет на правильную строку в базе данных.
Вставка в B + Tree
Вставка немного сложна по сравнению с запросом, потому что может случиться так, что узел, в который мы хотим вставить, уже заполнен. Разберемся в этом на примере. Будем считать, что мы хотим вставить в приведенную выше таблицу.
Первый шаг вставки - найти правильный листовой узел для этого запроса. В простом случае мы хотим вставить какое-то слово, которое находится между «Мианус» и «Перриридж». В этом случае мы можем просто добавить новое слово во второе слева слева (справа от «Mianus»).
Предыдущий случай был очень простым, теперь перейдем к немного хитрому. Допустим, мы хотим вставить «Clearview» в наше дерево. Мы легко можем видеть, что правильная позиция «Clearview» - это первый листовой узел, но он уже содержит максимальное количество ключей. Следовательно, в этом случае нам придется создать новый листовой узел, а затем перераспределить эти n ключей (n-1 в предыдущем узле и 1 добавлен) в эти два новых узла. Обычно мы помещаем первые ключи ceil (n / 2) в первый лист, а остальные - во второй.
Теперь нам нужно добавить этот вновь сформированный узел в дерево. Мы добавим первый ключ нового узла в родительский. В нашем случае нам нужно добавить «Центр города» к родительскому узлу. После этого дерево выглядит так
Этот случай можно усложнить, если мы добавим «Алабама». В таком случае родитель («центр» и «Майнус» тоже заполнен). Но описанную выше процедуру можно повторить еще раз, и это можно делать итеративно. Однако, если мы увидим, что все узлы до корневого узла полностью заполнены, нам придется добавить новый уровень, чтобы разместить больше ключей.
Удаление в B + дереве
Если вы поняли, что такое вставка, это будет довольно просто. Прежде всего, нам нужно найти листовой узел, из которого нужно удалить ключ. Давайте сначала предположим, что изначально дерево выглядело как
Теперь мы хотим удалить из этого «Даунтаун». Мы видим, что его удаление сделает листовой узел пустым, и, следовательно, нам придется удалить этот узел из его родителя. Это уменьшит один указатель от его родителя. Но интересно то, что этот узел по-прежнему действителен как 2 ›ceil (n / 2). Таким образом, нам больше не нужно двигаться вверх, и мы успешно удалили «Центр города». Результирующее дерево выглядит так
А теперь перейдем к немного каверзному случаю. Теперь предположим, что мы хотим удалить «Перририджа» из приведенного выше дерева. Мы видим, что его удаление не только сделает корень листа пустым, но и сделает его родительский элемент недействительным, поскольку теперь с ним будет связан только один указатель. В таком случае нам нужно будет увидеть узлы-братья (в данном случае «Mianus»). У этого брата есть место для размещения этого родительского узла, и, следовательно, эти два будут объединены, чтобы сформировать один узел. Кроме того, корневой узел также станет недействительным, поскольку теперь у него будет только один указатель, и, следовательно, он также будет удален, а высота дерева уменьшится на 1.
В отличие от предыдущего случая, может случиться так, что соседний узел также заполнен и не может вместить. Например, мы хотим удалить «Perryridge» с рис. 5. Теперь мы видим, что родственный узел «Redwood» заполнен. В таком случае мы перераспределяем указатели таким образом, чтобы у каждого брата и сестры было почти одинаковое количество указателей. Решение для этого было бы.
Как правило, всякий раз, когда мы выполняем удаление, мы движемся к корню и пытаемся сделать все узлы на пути действительными, выполняя одну из операций, описанных выше.
Спасибо за прочтение. :)
