285
правок
Изменения
→Добавление ключа
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
=== Добавление ключа ===
<wikitex>[[Файл:B3inssp.png|thumb|right|500px|Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу]][[Файл:B3insa.png|thumb|400px|right|Вставка ключей в дерево с t=3, т.е. узлы могут держать не более 5 ключей]]Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. Добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев. Если и родительский узел заполнен заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
Добавление ключа в B-дереве может быть осуществлена за один нисходящий проход от корня к листу. Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. При проходе от корня к листьям в поисках места для нового ключа будут разбиваться все заполненные узлы, которые будут пройдены (включая и сам лист). Таким образом, если надо разбить какой-то полный узел, гарантируется, что его родительский узел не будет заполнен.
Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(t \log_g log_t n)$ процессорного времени.
B-Tree-Insert(T, k)
r = T.root
s.leaf = FALSE
s.n = 0
s.$C_1$ c[1] = r
B-Tree-Split-Child(s, 1)
B-Tree-Insert-Nonfull(s, k)
i = x.n
if x.leaf
while (i $\geqslant$ >= 1 && k $<$ x.$key_i$key[i]): x.$key_{key[i+1}$ ] = x.$key_i$key[i]
i = i - 1
x.$key_{key[i+1}$ ] = k
x.n = x.n + 1
Disk-Write(x)
else
while (i $\geqslant$ >= 1 && k < x.$key_i$key[i]):
i = i - 1
i = i + 1
Disk-Read(x.$c_i$)
if x.$c_i$c[i].n == 2t - 1
B-Tree-Split-Child(x, i)
if k > x.$key_i$key[i]
i = i + 1
B-Tree-Insert-Nonfull(x.$c_i$c[i], k)
Функция $\operatorname{B-Tree-Insert-Nonfull}$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове.
