1632
правки
Изменения
м
rollbackEdits.php mass rollback
Функция <tex>\operatorname{B-Tree-Split-Child}</tex> получает в качестве входного параметра незаполненный внутренний узел <tex>x</tex> (находящийся в оперативной памяти), индекс <tex>t</tex> и узел <tex>y</tex> (также находящийся в оперативной памяти), такой что <tex>y = c_i[x]</tex> является заполненным дочерним узлом <tex>x</tex>. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля <tex>x</tex>, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на <tex>1</tex>. Отметим, что увеличить высоту B-дерева можно только разбиением.
[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с <tex>t=4</tex>]]
'''void''' B-Tree-Split-Child(x: '''Node''', t: '''int''', i: '''int'''):
Disk-Write(z)
Disk-Write(x)
=== Удаление ключа ===
[[Файл:B3dell.PNG|550px|Удаление <tex>F</tex> из листа]]
В противном случае, если существует соседний лист с тем же родителем, который содержит больше <tex>t - 1</tex> ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как <tex>k_1</tex>. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим <tex>k_2</tex>. Удалим из исходного узла листключ, который нужно было удалить, спустим в этот узел <tex>k_2</tex>, а вместо <tex>k_2</tex> в родительском узле поставим <tex>k_1</tex>. Если все соседи содержат по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переместим]] в новый узел.
==== Удаление ключа из внутреннего узла ====
== Вариации B-дерева ==
=== B+-дерево ===
В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
=== B*-дерево ===
== См. также ==
* [[2-3 дерево]]
* [[B+-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
