Вставка

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

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

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

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

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