B+-дерево

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

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

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

Структура

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

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

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

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

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

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

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

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

Операции

$B^{+}$-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте, то есть $O(\log n)$. Однако стоит заметить, что так как степень дерева зачастую выбирается большой, константа при выполнении операций тоже большая. Это связано с большим количеством ключей в узлах, которые необходимо сравнить. Но из-за небольшой высоты дерева это не сильно сказывается на скорости работы.

Поиск листа

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

Node find_leaf(T: BPlusTree, key: int):
    cur = T.root
    while cur.leaf $\neq$ true
        for i = 0 to cur.key_num
            if i == cur.key_num or key < cur.key[i]
                cur = cur.child[i]
                break
    return cur

Поиск

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

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

Ищем лист, в который можно добавить ключ и добавляем его в список ключей. Если узел не заполнен, то добавление завершено. Иначе разбиваем узел на два узла. Будем считать, что в дереве не может находиться $2$ одинаковых ключа, поэтому $insert$ будет возвращать был ли добавлен ключ.

bool insert(T: BPlusTree, key: int, value: Info):
    leaf = find_key(T, key)
    if key $\in$ leaf
        return false 
    
    while pos < leaf.key_num and leaf.key[pos] < key
        ++pos
    Вставляем key и value на позицию pos в листе
    ++leaf.key_num
    
    if leaf.key_num == 2 * t              // t — степень дерева
        split(T, leaf)                   // Разбиваем узел
    return true

Разбиение узла

Разбиение на два узла происходит следующим образом: в первый добавляем первые $t$ ключей, во второй последние $t - 1$. Если узел — лист, то оставшийся ключ также добавляется в правое поддерево, а его копия отправляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.

Если и родительский узел заполнен — поступаем аналогично, но не копируем, а просто перемещаем оставшийся перемещаем ключ в родительский узел, так как это просто копия. Повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.

Поскольку в родителя всегда отправляется минимальный ключ из второй половины, то каждый ключ, который хранится во внутренней вершине — это минимум правого поддерева для этого ключа.

void split(T: BPlusTree, node: Node):
    Создаем новый узел new_node
    Перенаправляем right и left указатели, вставляя его между node и node.right
    mid_key = node.key[t]
    
    new_node.key_num = t - 1     
    node.key_num = t
    Перемещаем new_node.key_num значений и соответствующих им указателей в new_node
     
    if node.leaf
        new_node.leaf = true
        Перемещаем в new_node оставшийся при разбиении элемент
    
    if node == T.root
        Создаем новый корень T.root
        T.root.key[0] = mid_key
        T.root.child[0] = node
        T.root.child[1] = new_node
        T.root.key_num = 1;
        node.parent = T.root
        new_node.parent = T.root
    else
        new_node.parent = node.parent
        parent = node.parent
        
        pos = 0
        while pos < parent.key_num and parent.key[pos] < mid_key
            ++pos
        Вставляем в parent на позицию pos ключ mid_key и направляем ссылку из него на new_node
        ++parent.key_num
        
        if parent.key_num == 2 * t        // Если требуется, продолжаем разбиение узла
            split(T, parent)

Удаление

Поскольку все ключи находятся в листах, для удаления в первую очередь необходимо найти листовой узел, в котором он находится. Если узел содержит не менее $t - 1$ ключей, где $t$ — это степень дерева, то удаление завершено. Иначе необходимо выполнить попытку перераспределения элементов, то есть добавить в узел элемент из левого или правого брата (не забыв обновить информацию в родителе). Если это невозможно, необходимо выполнить слияние с братом и удалить ключ, который указывает на удалённый узел. Объединение может распространяться на корень, тогда происходит уменьшение высоты дерева. Так как мы считаем, что в дереве не может находиться $2$ одинаковых ключей, то $delete$ будет возвращать был ли удален ключ.

bool delete(T: BPlusTree, key: int):
    leaf = find_key(T, key)
    pos = 0
    if key $\notin$ leaf
        return false 
    else 
        delete_in_node(leaf, key)                                   // Удалить ключ из вершины
        return true

void delete_in_node(tec: Node, key: int):
    pos = 0
    while pos < tec.key_num and tec.key[pos] < key
        ++pos
    if key $\notin$ tec
        return 
    Удаляем key из tec
    --tec.key_num
    
    if leaf.key_num < t - 1
        right_sibling = tec.right
        left_sibling = tec.left
        if left_sibling $\neq$ null and left_sibling.key_num > t - 1
            --left_sibling.key_num
            ++tec.key_num
            Перемещаем максимальный из left_sibling ключ на первую позицию в tec
            Обновляем ключи на пути к корню
        
        else if right_sibling $\neq$ null and right_sibling.key_num > t - 1
            --right_sibling.key_num
            ++tec.key_num
            Перемещаем минимальный из right_sibling ключ на последнюю позицию в tec
            Обновляем ключи на пути к корню
         
        else
            if left_sibling $\neq$ null 
                Сливаем tec и left_sibling 
                Перенаправляем right и left указатели
                Обновляем ключи на пути к корню
                delete_in_node(left_sibling.parent, min_key(tec))    // Удаляем разделительный ключ в отце
             
            else
                Сливаем tec и right_sibling 
                Перенаправляем right и left указатели
                Обновляем ключи на пути к корню
                delete_in_node(tec.parent, min_key(right_sibling)) 
           
        if T.root.key_num == 1                                       // Если у корня 1 ребенок понижаем высоту дерева
            T.root = T.root.child[0]

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

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

См. также

• B-дерево
• 2-3 дерево

Источники информации

• Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
• Wikipedia — B Plus tree
• Wikipedia — B tree
• B plus tree visualization