Удаление

При удалении необходимо найти блок В, в котором содержится запись v. Если после удаления в блоке осталось е или более записей, то после удаления найденной записи и сдвига всех остальных операция закончена.

Если удаляемая запись является первой в блоке, то необходимо изменить значения в блоках в направлении обратном найденному пути. При этом необходимо учитывать следующее. Если В первый потомок своего предка, то предок не включает значения для ключа первой записи блока В. В этом случае нужно проверить предка предка и так далее, пока не найдется блок-предок А1 для В, такой что, А1 – не первый потомок своего предка А2. Тогда новое меньшее значение ключа блока В записывают в блок А2 вместе с адресом блока А1.

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