286
правок
Изменения
Нет описания правки
== Отличия от B-дерева ==
В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B<tex>^{+}</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>-дерева не более чем на 1 отличается от [[B-дерево#Высота|высоты B-дерева]], то есть хранение информации только в листах почти не ухудшает эффективность дерева
== Структура ==
'''Node''' child[] <span style="color:#008000"> // указатели на детей узла</span>
'''Info''' pointers[] <span style="color:#008000">// если лист {{---}} указатели на данные</span>
'''Node''' next left<span style="color:#008000"> // указатели указатель на следующий узеллевого брата</span> '''Node''' right <span style="color:#008000"> // указатель на правого брата</span>
=== Структура дерева ===
'''struct''' BPlusTree
'''Node''' root <span style="color:#008000"> // указатель на корень дерева</span>
== Операции ==
leaf.pointers[pos + 1] = value
++leaf.key_num
'''if''' leaf.key_num == 2*t <span style="color:#008000"> // t {{---}} степень дерева</span> split(T, leaf) <span style="color:#008000"> // Разбиваем узел</span>
'''return true'''
'''void''' split(T: '''BPlusTree''', node: '''Node'''):
new_node = new_Node() <span style="color:#008000"> //Создаем новый узел</span>
new_node.right = node.right node.right.left = new_node node.next right = new_node new_node.left = node mid_key = node.key[t- 1]
new_node.key_num = t
'''for''' i = 0 '''to''' new_node.key_num - 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] new_node.pointers[new_node.key_num] = node.pointers[2*t- 1] new_node.child[new_node.key_num] = node.child[2*t- 1]
node.key_num = t - 1
++node.key_num
new_node.leaf = '''true'''
mid_key = node.key[t + 1]
'''if''' node == T.root
'''if''' parent.key_num == 2*t
split(T, parent)
=== Удаление ===
Поскольку все ключи находятся в листах, для удаления в первую очередь необходимо найти листовой узел, в котором он находится. Если узел содержит не менее <tex>t - 1</tex> ключей, где <tex>t</tex> {{---}} это степень дерева, то удаление завершено. Иначе необходимо выполнить попытку перераспределения элементов, то есть добавить в узел элемент из левого или правого брата (не забыв обновить информацию в родителе). Если это невозможно, необходимо выполнить слияние с братом и удалить ключ, который указывает на удалённый узел. Объединение может распространяться на корень, тогда происходит уменьшение высоты дерева.
== Примeчания ==
<references/>
