285
правок
Изменения
→Разбиение узла
=== Разбиение узла ===
[[Файл:B3splt.jpg|thumb|350px|Разбиение узла B-дерева с t=4]]<wikitex>Функция B-Tree-Split-Child получает в качестве входного параметра незаполненный внутренний узел $x$ (находящийся в оперативной памяти), индекс $t$ и узел $y$ (также находящийся в оперативной памяти), такой что у = $c_i$ $[x]$ является заполненным дочерним узлом $x$. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля $x$, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на 1. Разбиение — единственное средство увеличения высоты B-дерева.
B-Tree-Split-Child(x, i)
{
z = Allocate-Node()
y = x.$C_i$
z.leaf = y.leaf
z.n = t - 1
for j = 1 to t - 1
z.$key_j$ = y.$key_{j+t}$
if not y.leaf
for j = 1 to t
z.$c_j$ = y.$c_{j+t}$
y.n = t - 1
for j = x.n + 1 downto i + 1
x.$C_{j+1}$ = x.$C_j$
$x.c_{i+1}$ = z
for j = x.n downto i
x.$key_{j+1}$ = x.$key_j$
x.$key_i$ = y.$key_t$
x.n = x.n + 1
Disk-Write(y)
Disk-Write(z)
Disk-Write(x)
}
</wikitex>
=== Слияние ===
