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