B+-дерево

B[math]^{+}[/math]-дерево (англ. B[math]^{+}[/math]-tree) — структура данных на основе B-дерева, сбалансированное [math]n[/math]-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B[math]^{+}[/math]-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.

Где используется

Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS, ReiserFS, NSS, JFS, ReFS. Различные реляционные системы управления базами данных, такие как Microsoft SQL Server, Oracle Database, SQLite используют B[math]^{+}[/math]-деревья для табличных индексов.

Отличия от B-дерева

В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B[math]^{+}[/math]-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев.

Структура

Свойства B[math]^{+}[/math] дерева аналогичны свойствам B-дерева (с учетом отличий описанных выше).

Структура узла

struct Node
   bool leaf       // является ли узел листом
   int  key_num    // количество ключей узла
   int  key[]      // ключи узла
   Node parent     // указатель на отца
   Node child[]    // указатели на детей узла
   Info pointers[] // если лист — указатели на данные
   Node next       // указатели на следующий узел

Структура дерева

struct BPlusTree
   int  t          // минимальная степень дерева
   Node root       // указатель на корень дерева

Оценка высоты дерева

Теорема:

Если [math]n \geqslant 1[/math], то для B[math]^{+}[/math]-дерева c [math]n[/math] узлами и минимальной степенью [math]t \geqslant 2[/math] [math]h \leqslant \log_t\dfrac{n}{2} + 1[/math]

Доказательство:

[math]\triangleright[/math]

Так как [math]n \geqslant 1[/math], то корень B[math]^{+}[/math]-дерева [math]T[/math] содержит хотя бы один ключ, а все остальные узлы — хотя бы [math]t - 1[/math] ключей. [math]T[/math] имеет хотя бы [math]2[/math] узла на высоте [math]1[/math], не менее [math]2t[/math] узлов на глубине [math]2[/math], и так далее. То есть на глубине [math]h[/math], оно имеет хотя бы [math]2t^{h-1}[/math] узлов. Так как сами ключи хранятся только в листах, а во внутренних вершинах лишь их копии, то для [math]n[/math] ключей [math]n \geqslant 2t^{h-1}[/math] [math]t^{h-1} \leqslant \dfrac{n}{2}[/math] [math]h-1 \leqslant \log_t\dfrac{n}{2}[/math] [math]h \leqslant \log_t\dfrac{n}{2} + 1[/math]

[math]\triangleleft[/math]

Как можно заметить, высота B[math]^{+}[/math]-дерева не более чем на 1 отличается от высоты B-дерева, то есть хранение информации только в листах почти не ухудшает эффективность дерева

Операции

B[math]^{+}[/math]-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте.

Поиск листа

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

Node find_leaf(T: BPlusTree, k: int):
    now = T.root
    while !now.leaf
        for i = 0 to now.key_num
            if i == now.key_num or key < now.key[i]
                now = now.ch[i]
                break
    return now

Поиск

Находим нужный лист через [math]find[/math]_[math]leaf[/math] и ищем нужный ключ в нем

Добавление ключа

Ищем лист, в который можно добавить ключ и добавляем его в список ключей. Если узел не заполнен, то добавление завершено. Иначе разбиваем узел на два узла, в первый добавляем первые [math]t - 1[/math] ключей, во второй оставшиеся [math]t[/math]. Первый ключ их второго узла копируется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.

Если и родительский узел заполнен — поступаем аналогично, но не копируем, а перемещаем ключ в родительский узел, так как это просто копия. Повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается. Будем считать, что в дереве не может находиться 2 одинаковых ключа, поэтому [math]insert[/math] будет возвращать был ли добавлен ключ.

void insert(T: BPlusTree, key: Node, value: Info):
    leaf = find_key(T, key)
    for i = 0 to leaf.key_num
        if key == leaf.key[i]
            return false 
    pos = 0
    while pos < leaf.key_num and leaf.key[pos] < key
        ++pos
    for i = leaf.key_num downto pos + 1 
        leaf.key[i] = leaf.key[i-1]
    for i = leaf.key_num + 1 downto pos + 2 
        leaf.pointers[i] = leaf.pointer[i-1]
    leaf.key[pos] = key
    leaf.pointers[x + 1] = value
    ++leaf.key_num
    if leaf.key_num == M       // M - степень дерева
        split(T, leaf)