Изменения

'''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>-деревья для табличных индексов.

В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B<tex>B^{+}</tex>-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев. == Оценка высоты дерева =={{Теорема|statement=Если <tex>n \geqslant 1</tex>, то для B<tex>^{+}</tex>-дерева c <tex>n</tex> узлами и минимальной степенью <tex>t \geqslant 2</tex> высота:<tex>h \leqslant \log_t\dfrac{n}{2} + 1</tex>|proof=Так как <tex>n \geqslant 1</tex>, то корень B<tex>^{+}</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> ключей <tex>n \geqslant 2t^{h-1}</tex> :<tex>t^{h-1} \leqslant \dfrac{n}{2}</tex> :<tex>h-1 \leqslant \log_t\dfrac{n}{2}</tex> :<tex>h \leqslant \log_t\dfrac{n}{2} + 1</tex>}}  Как можно заметить, высота B<tex>^{+}</tex>-дерева не более чем на <tex>1</tex> отличается от [[B-дерево#Высота|высоты B-дерева]], то есть хранение информации только в листах почти не ухудшает эффективность дерева

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

B<tex>B^{+}</tex>-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте., то есть <tex>O(\log_tn)</tex>

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

mid_key = node.key[t - 1] new_node.key_num = t- 1

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]

node.key_num = t - 1

++nodenew_node.key_num

mid_key '''for''' i = new_node.key_num - 1 '''downto''' 1 new_node.key[i] = node.key[i - 1] new_node.pointers[i] = node.pointers[i - 1] new_node.key[0] = node.key[t] new_node.pointers[0] = node.pointers[0]

delete_in_node(left_sibling.parent, max_keymin_key(left_siblingtec)) <span style="color:#008000"> // Удаляем разделительный ключ в отце</span>

delete_in_node(tec.parent, max_keymin_key(tecright_sibling))

* [https://en.wikipedia.org/wiki/B%2B_tree Wikipedia {{---}} B<tex>B^{+}</tex>-tree]

* [https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html B<tex>B^{+}</tex>-tree visualization]