Изменения

'''B<tex>B^{+}</tex>-дерево''' (англ. ''B<tex>B^{+}</tex>-tree'') {{---}} структура данных на основе [[B-дерево|B-дерева]], сбалансированное <tex>n</tex>-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B<tex>B^{+}</tex>-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка <tex>100 </tex> или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве. == Где используется ==Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения {{---}} в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS<ref>[[wikipedia:NTFS |Wikipedia {{---}} NTFS]]</ref>, ReiserFS<ref>[[wikipedia:ReiserFS |Wikipedia {{---}} ReiserFS]]</ref>, NSS<ref>[[wikipedia:Novell Storage Services |Wikipedia {{---}} NSS]]</ref>, JFS<ref>[[wikipedia:JFS (file system) |Wikipedia {{---}} JFS]]</ref>, ReFS<ref>[[wikipedia:ReFS |Wikipedia {{---}} ReFS]]</ref>. Различные реляционные системы управления базами данных, такие как Microsoft SQL Server<ref>[[wikipedia:Microsoft SQL Server|Wikipedia {{---}} Microsoft SQL Server]]</ref>, Oracle Database<ref>[[wikipedia:Oracle Database|Wikipedia {{---}} Oracle Database]]</ref>, SQLite<ref>[[wikipedia:SQLite|Wikipedia {{---}} SQLite]]</ref> используют B<tex>^{+}</tex>-деревья для табличных индексов.

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

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

'''Node''' next left<span style="color:#008000"> // указатели указатель на следующий узеллевого брата</span> '''Node''' right <span style="color:#008000"> // указатель на правого брата</span>

{{Теорема|statement=Если <tex>n \geqslant 1</tex>, то для B<tex>B^{+}</tex>-дерева c <tex>n</tex> узлами и минимальной степенью <tex>t \geqslant 2</tex>высота

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

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

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

'''Node''' find_leaf(T: '''BPlusTree''', kkey: '''int'''): now cur = T.root '''while''' !nowcur.leaf<tex>\neq</tex> true '''for''' i = 0 '''to''' nowcur.key_num '''if''' i == nowcur.key_num '''or''' key < nowcur.key[i] now cur = nowcur.chchild[i]

'''return''' nowcur

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

'''for''' i = 0 '''to''' leaf.key_num '''if''' key == <tex>\in</tex> leaf.key[i] '''return false''' <span style="color:#008000">// Ищем позицию для нового ключа </span>

leaf.key[i] = leaf.key[i-1] '''for''' i = leaf.key_num + 1 '''downto''' pos + 2 leaf.pointers[i] = leaf.pointer[i-1]

leaf.pointers[pos + 1] = value

'''if''' leaf.key_num == 2 * t <span style="color:#008000"> // t {{---}} степень дерева</span> split(T, leaf) <span style="color:#008000"> // Разбиваем узел</span>

Разбиение на два узла происходит следующим образом: в первый добавляем первые <tex>t - 1</tex> ключей, во второй оставшиеся последние <tex>t- 1</tex>. Первый Если узел {{---}} лист, то оставшийся ключ из второго узла копируется также добавляется в правое поддерево, а его копия отправляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.  Если и родительский узел заполнен {{---}} поступаем аналогично, но не копируем, а просто перемещаем оставшийся перемещаем ключ в родительский узел, так как это просто копия. Повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается. Поскольку в родителя всегда отправляется минимальный ключ из второй половины, то каждый ключ, который хранится во внутренней вершине {{---}} это минимум правого поддерева для этого ключа. [[Файл:B Plus tree insetring.png|1000px]]

new_node = new_Node() <span style="color:#008000"> //Создаем новый узел</span> <span style="color:#008000">// Перенаправляем right и left указатели</span> new_node.right = node.right node.next right.left = new_node node.right = new_node new_node.left = node <span style="color:#008000">// Перемещаем t - 1 значений и соответствующих им указателей в new_node</span>

new_node.key_num = t- 1 node.key_num = t

new_node.key[i] = node.key[i + t+ 1] new_node.pointers[i] = node.pointers[i + t+ 1] new_node.child[i] = node.child[i + t+ 1] new_node.pointers[new_node.key_num] = node.pointers[2*t] new_node.child[new_node.key_num] = node.child[2*t] node.key_num = t - 1

++nodenew_node.key_num

<span style="color:#008000">// Перемещаем в new_node оставшийся при разбиении элемент mid_key </span> '''for''' i = new_node.key_num - 1 '''downto''' 1 new_node.key[i] = new_node.key[i - 1] new_node.pointers[i] = new_node.pointers[i - 1] new_node.key[0] = node.key[t + 1] new_node.pointers[0] = node.pointers[t]

T.root = new_Node()<span style="color:#008000"> // Создаем новый корень T.root </span>

parent.key[i] = parent.key[i-1]

parent.child[i] = parent.child[i-1]

'''if''' parent.key_num == 2*t