285
правок
Изменения
→Добавление ключа
Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(t \log_g n)$ процессорного времени.
B-Tree-Insert(T, k)
r = T.root
if (r.n == 2t - 1) {
s = Allocate-Node()
T.root = s
B-Tree-Split-Child(s, 1)
B-Tree-Insert-Nonfull(s, k)
else
B-Tree-Insert-Nonfull(r, k)
B-Tree-Insert-Nonfull(x, k)
i = x.n
if x.leaf
while (i $\geqslant$ 1) && (k $<$ x.$key_i$) {
x.$key_{i+1}$ = x.$key_i$
i = i - 1
x.$key_{i+1}$ = k
x.n = x.n + 1
Disk-Write(x)
else { while (i $\geqslant$ 1) && (k < x.$key_i$)
i = i - 1
i = i + 1
Disk-Read(x.$c_i$)
if x.$c_i$.n == 2t - 1
B-Tree-Split-Child(x, i)
if k > x.$key_i$
i = i + 1
B-Tree-Insert-Nonfull(x.$c_i$, k)
Функция $\operatorname{B-Tree-Insert-Nonfull}$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове. Использование функции $\operatorname{B-Tree-Split-Child}$ гарантирует, что рекурсия не встретится с заполненным узлом.
</wikitex>
