285
правок
Изменения
м
→Добавление ключа
Добавление ключа в B-дереве может быть осуществлена за один нисходящий проход от корня к листу. Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. При проходе от корня к листьям в поисках места для нового ключа будут разбиваться все заполненные узлы, которые будут пройдены (включая и сам лист). Таким образом, если надо разбить какой-то полный узел, гарантируется, что его родительский узел не будет заполнен.
[[Файл:B3inssp.png|500px550px|Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]
Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(t \log_t n)$ процессорного времени.
B-Tree-Insert(T, k)
Использование функции $\operatorname{B-Tree-Split-Child}$ гарантирует, что рекурсия не встретится с заполненным узлом.
[[Файл:B3insa.png|450px550px|Вставка ключей B, Q, L и F в дерево с t=3, т.е. узлы могут держать содержать не более 5 ключей]]
</wikitex>
