Удаление
Следуя примеру большинства работ по B-деревьям, мы вводим процедуру отложенного удаления . Данный подход широко используется в базах данных, т.к. процедура удаления для B-деревьев может быть сложнее процедуры вставки. Отложенное (lazy) удаление позволяет, во-первых, значительно упростить само удаление; во-вторых, ускорить обновления базы данных. Удаление заключается в простом снятии флага final с найденного узла. После удаления узла таким образом мы получаем избыточный узел, и, следовательно, неминимальное дерево.
При таком подходе необходима процедура минимизации дерева (или, возможно, отдельной ветки). Она заключается в удалении всех избыточных вершин. Избыточные вершины бывают двух типов:
- Вершины, которые не помечены как final, и у которых нет исходящих рёбер. Такие вершины можно просто удалить.
- Вершины, которые не помечены как final из которых есть ровно одно исходящее ребро. В этом случае вершины достаточно объединить конкатенацией префиксов через символ ребра.
В результате применения этой операции не остаётся избыточных вершин. В результате такой операции может получится так, что в некоторой ветке не останется вершин, либо останется единственная external-вершина. Такую ветку необходимо удалить, а (единственную) дочернюю ветку перенести вверх на данную страницу. Может оказаться так, что страницу необходимо будет для этого разделить. Таким образом минимизация одной ветки затрагивает не более четырёх страниц (три страницы может затронуть разделение, и с одной страницы мы переносим ветку)
