Вставка

Поиск

Начиная с корня, ищем ключ К среди ключей узла. Если поиск удачен, то операция завершается. Если же поиск неудачен, и нужный ключ имеет значение между K_i и K_i+1, спускаемся вниз по связи P_i и повторяем процесс. В конце концов, алгоритм либо найдет ключ, либо выйдет на пустую связь, что означает, что искомого ключа в дереве нет.

Вставка всегда выполняется в лист. Место для вставки обнаруживается описанным выше процессом поиска. Если узел, в который должна быть выполнена вставка, содержит меньше m-1 ключей, то помещаем новый ключ в узел и на этом операция заканчивается. Если же узел уже содержит максимально возможное число ключей, то выберем соседний неполный узел. Допустим, что это сосед слева, и рассмотрим множество ключей, состоящее из ключей левого соседа, разделяющего ключа в отце и ключей переполнившегося узла как на рис. 49.

Рис. 49 Вставка ключа в В-дерево

Средний ключ поместим на место разделяющего, ключи слева от него передадим левому соседу, ключи справа от него поместим в узел, в котором произошло переполнение.

Если же не найдется соседа, которому можно было бы передать лишний ключ, то узел, в котором произошло переполнение, расщепляется на два, средний ключ поднимается к отцу, а оставшиеся ключи делятся пополам между двумя узлами. Рис 50 иллюстрирует операцию. Передача ключа в узел отца может вызвать его расщепление. Процесс расщеплений может рекурсивно подняться до корня и расщепить его. В этом случае создается новый корень, содержащий единственный ключ.

Рис 50. Расщепление узла при вставке ключа в В-дерево