Изменения

<wikitex>Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. Добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев. Если и родительский узел заполнен заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.Добавление ключа в B-дереве может быть осуществлена за один нисходящий проход от корня к листу. Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. При проходе от корня к листьям в поисках места для нового ключа будут разбиваться все заполненные узлы, которые будут пройдены (включая и сам лист). Таким образом, если надо разбить какой-то полный узел, гарантируется, что его родительский узел не будет заполнен. Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(tlog_g n)$ процессорного времени. $B-TREE-INSERT (T, k)$ { $r = T.root$ $if (r.n == 2t - 1)$ { $s = ALLOCATE-NODE()$ $T.root = s$ $s.leaf = FALSE$ $s.n = 0$ $s.c_1 = r$ $B-TREE-SPLIT-CHILD(s, 1)$ $B-TREE-INSERT-NONFULL(s, k)$ } $else$ $B-TREE-INSERT-NONFULL(r, k)$ }</wikitex>