Изменения

Перейти к: навигация, поиск

B+-дерево

1883 байта убрано, 04:04, 13 апреля 2018
Нет описания правки
'''bool''' insert(T: '''BPlusTree''', key: '''int''', value: '''Info'''):
leaf = find_key(T, key)
'''for''' i = 0 '''to''' leaf.key_num '''if''' key == <tex>\in</tex> leaf.key[i] '''return false''' pos = 0
'''while''' pos < leaf.key_num '''and''' leaf.key[pos] < key
++pos
'''for''' i = leaf.key_num '''downto''' pos + 1 leaf.Вставляем key[i] = leaf.key[i - 1] leaf.pointers[i] = leaf.pointer[i - 1] leaf.key[и value на позицию pos] = key 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> new_node.right = node.right node.Перенаправляем right.и left = new_node указатели, вставляя его между node и node.right = new_node new_node.left = node
mid_key = node.key[t]
new_node.key_num = t - 1
'''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.child[new_node.key_num] = node.child[2 * t]
node.key_num = t
Перемещаем new_node.key_num значений и соответствующих им указателей в new_node
'''if''' node.leaf
++new_node.key_num
new_node.leaf = '''true'''
'''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]и оставшийся при разбиении элемент
'''if''' node == T.root
Создаем новый корень T.root = new_Node()
T.root.key[0] = mid_key
T.root.child[0] = node
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 <span style="color:#008000"> // Если требуется, продолжаем разбиение узла</span>
split(T, parent)
leaf = find_key(T, key)
pos = 0
'''while''' pos < leaf.key_num '''and''' leaf.key[pos] < key ++pos '''if''' pos == leaf.key_num '''or''' leaf.key[pos] <tex>\neqnotin</tex> keyleaf '''return false'''
'''else'''
delete_in_node(leaf, key) <span style="color:#008000"> // Удалить ключ из вершины</span>
'''while''' pos < tec.key_num '''and''' tec.key[pos] < key
++pos
'''if''' pos == tec.key_num '''or''' tec.key[pos] <tex>\neqnotin</tex> keytec '''returnfalse''' '''for''' i = pos '''to''' tec.key_num - 1 tec.key[i] = tec.Удаляем key[i + 1] tec.pointers[i] = tec.pointer[i + 1] '''for''' i = pos + 1 '''to''' tec.key_num tec.child[i] = из tec.child[i + 1]
--tec.key_num
--left_sibling.key_num
++tec.key_num
'''for''' i = 1 '''to''' tec.key_num - 1 tec.key[i] = tec.key[i - 1] tec.pointers[i] = tec.pointer[i - 1] tec.child[i] = tec.child[i - 1] tec.child[tec.key_num] = tec.child[tec.key_num - 1] tec.key[0] = Перемещаем максимальный из left_sibling.key[left_sibling.key_num] ключ на первую позицию в 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>
'''else if''' right_sibling <tex>\neq</tex> null '''and''' right_sibling.key_num > t - 1
--right_sibling.key_num
++tec.key_num
Перемещаем минимальный из left_sibling ключ на последнюю позицию в 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) Обновляем ключи на пути к корню
'''else'''
'''if''' left_sibling <tex>\neq</tex> null
Сливаем tec и left_sibling.right = tec.right tec.Перенаправляем right.и left = left_sibling '''for''' i = 0 to tec.key_num - 1 left_sibling.key[left_sibling.key_num] = tec.key[i] left_sibling.pointers[left_sibling.key_num] = tec.pointers[i] left_sibling.child[left_sibling.key_num + 1] = tec.child[i] ++left_sibling.key_numуказатели left_sibling.child[left_sibling.key_num + 1] = tec.child[tec.key_num] update(left_sibling) Обновляем ключи на пути к корню
delete_in_node(left_sibling.parent, min_key(tec)) <span style="color:#008000"> // Удаляем разделительный ключ в отце</span>
'''else'''
Сливаем tec и right_sibling.right.left = tec tec.Перенаправляем right = right_sibling.right '''for''' i = 0 to tec.key_num - 1 tec.key[tec.key_num] = right_sibling.key[i] tec.pointers[tec.key_num] = right_sibling.pointers[i] tec.child[tec.key_num + 1] = right_sibling.child[i] ++tec.key_num tec.child[tec.key_num + 1] = right_sibling.child[right_sibling.key_num]и left указатели update(tec)Обновляем ключи на пути к корню
delete_in_node(tec.parent, min_key(right_sibling))
'''if''' T.root.key_num == 1<span style="color:#008000"> // Если у корня 1 ребенок понижаем высоту дерева</span>
T.root = T.root.child[0]
Mervap
286
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/64902»

Навигация