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