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