Изменения
→Разбиение узла: Исправлен баг с перемещением mid_key в new_node
== Отличия от B-дерева ==
В <tex>B</tex>-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В <tex>B^{+}</tex>-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем <tex>B</tex>-деревьев.
== Структура ==
Свойства <tex>B^{+}</tex> дерева аналогичны [[B-дерево#Структура| свойствам <tex>B</tex>-дерева]] (с учетом отличий описанных выше).
=== Структура узла ===
}}
Как можно заметить, высота <tex>B^{+}</tex>-дерева не более чем на <tex>1</tex> отличается от [[B-дерево#Высота|высоты <tex>B</tex>-дерева]], то есть хранение информации только в листах почти не ухудшает эффективность дерева
== Операции ==
<tex>B^{+}</tex>-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте, то есть <tex>O(\log n)</tex>. Однако стоит заметить, что так как степень дерева зачастую выбирается большой, константа при выполнении операций тоже большая. Это связано с большим количеством ключей в узлах, которые необходимо сравнить. Но из-за небольшой высоты дерева это не сильно сказывается на скорости работы.
=== Поиск листа ===
'''Node''' find_leaf(T: '''BPlusTree''', key: '''int'''):
'''break'''
'''return''' nowcur
=== Поиск ===
'''bool''' insert(T: '''BPlusTree''', key: '''int''', value: '''Info'''):
leaf = find_key(T, key)
pos = 0
'''while''' pos < leaf.key_num '''and''' leaf.key[pos] < key
++pos
<span style="color:#008000">// Вставляем ключ</span>
'''for''' i = leaf.key_num '''downto''' pos + 1
leaf.key[i] = leaf.key[i - 1]
leaf.pointers[pos] = value
++leaf.key_num
'''if''' leaf.key_num == 2 * t <span style="color:#008000"> // t {{---}} степень дерева</span>
split(T, leaf) <span style="color:#008000"> // Разбиваем узел</span>
'''void''' split(T: '''BPlusTree''', node: '''Node'''):
new_node = new_Node() <span style="color:#008000"> //Создаем новый узел</span>
<span style="color:#008000">// Перенаправляем right и left указатели</span>
new_node.right = node.right
node.right.left = new_node
node.right = new_node
new_node.left = node
<span style="color:#008000">// Перемещаем t - 1 значений и соответствующих им указателей в new_node</span>
mid_key = node.key[t]
new_node.key_num = t - 1
node.key_num = t
'''for''' i = 0 '''to''' new_node.key_num - 1
new_node.key[i] = node.key[i + t + 1]
new_node.child[i] = node.child[i + t + 1]
new_node.child[new_node.key_num] = node.child[2 * t]
'''if''' node.leaf
++new_node.key_num
new_node.leaf = '''true'''
<span style="color:#008000">// Перемещаем в new_node оставшийся при разбиении элемент mid_key </span>
'''for''' i = new_node.key_num - 1 '''downto''' 1
new_node.key[i] = nodenew_node.key[i - 1] new_node.pointers[i] = nodenew_node.pointers[i - 1]
new_node.key[0] = node.key[t]
new_node.pointers[0] = node.pointers[0t]
'''if''' node == T.root
T.root = new_Node()<span style="color:#008000"> // Создаем новый корень T.root </span>
T.root.key[0] = mid_key
T.root.child[0] = node
new_node.parent = node.parent
parent = node.parent
<span style="color:#008000">// Ищем позицию mid_key в отце </span>
pos = 0
'''while''' pos < parent.key_num '''and''' parent.key[pos] < mid_key
++pos
<span style="color:#008000">// Добавляем mid_key в отца и направляем ссылку из него на new_node </span>
'''for''' i = parent.key_num '''downto''' pos + 1
parent.key[i] = parent.key[i - 1]
leaf = find_key(T, key)
pos = 0
'''else'''
delete_in_node(leaf, key) <span style="color:#008000"> // Удалить ключ из вершины</span>
'''void''' delete_in_node(tec: '''Node''', key: '''int'''):
'''if''' key <tex>\notin</tex> tec
'''return'''
<span style="color:#008000">// Ищем позицию удаляемого ключа </span>
pos = 0
'''while''' pos < tec.key_num '''and''' tec.key[pos] < key
++pos
'''for''' i = pos '''to''' tec.key_num - 1
tec.key[i] = tec.key[i + 1]
--left_sibling.key_num
++tec.key_num
<span style="color:#008000">// Перемещаем максимальный из left_sibling ключ на первую позицию в tec </span>
'''for''' i = 1 '''to''' tec.key_num - 1
tec.key[i] = tec.key[i - 1]
tec.pointers[0] = left_sibling.pointers[left_sibling.key_num]
tec.child[0] = left_sibling.child [left_sibling.key_num + 1]
update(tec) <span style="color:#008000"> // Обновить ключи на пути к корню</span>
--right_sibling.key_num
++tec.key_num
<span style="color:#008000">// Перемещаем минимальный из right_sibling ключ на последнюю позицию в tec </span>
tec.key[tec.key_num - 1] = right_sibling.key[0]
tec.pointers[tec.key_num - 1] = right_sibling.child[0]
tec.child[tec.key_num - 1] = right_sibling.pointers[0]
update(tec) <span style="color:#008000"> // Обновить ключи на пути к корню</span>
'''else'''
'''if''' left_sibling <tex>\neq</tex> null
'''for''' i = 0 to tec.key_num - 1
left_sibling.key[left_sibling.key_num] = tec.key[i]
++left_sibling.key_num
left_sibling.child[left_sibling.key_num + 1] = tec.child[tec.key_num]
<span style="color:#008000">// Перенаправляем right и left указатели</span> left_sibling.right = tec.right tec.right.left = left_sibling update(left_sibling) <span style="color:#008000"> // Обновить ключи на пути к корню</span> delete_in_node(left_sibling.parent, min_key(tec)) <span style="color:#008000"> // Удаляем разделительный ключ в отце</span>
'''else'''
'''for''' i = 0 to tec.key_num - 1
tec.key[tec.key_num] = right_sibling.key[i]
++tec.key_num
tec.child[tec.key_num + 1] = right_sibling.child[right_sibling.key_num]
<span style="color:#008000">// Перенаправляем right и left указатели</span> right_sibling.right.left = tec tec.right = right_sibling.right update(tec) <span style="color:#008000"> // Обновить ключи на пути к корню</span> delete_in_node(tec.parent, min_key(right_sibling)) <span style="color:#008000"> // Удаляем разделительный ключ в отце</span>
'''if''' T.root.key_num == 1
T.root = T.root.child[0]
