286
правок
Изменения
→Вариации B-дерева
Функция <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)
=== Удаление ключа ===
== Вариации B-дерева ==
=== B+-дерево ===
В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
=== B*-дерево ===
== См. также ==
* [[2-3 дерево]]
* [[B+-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
