Вставка
Процедура добавления строки устроена таким образом, что она сначала строит структуру, описывающую изменение страницы, в которую надо вставить новые вершины. Может случиться, что для вставки нет места в странице. В этом случае процедура вызывает расширение дерева на необходимую величину, и вставка не происходит. Она должна быть вызвана ещё раз. Заметим также, что корень дерева может измениться в процессе работы процедуры.
Сама процедура добавления достаточно проста, однако она слишком велика, чтобы приводить её здесь. Опишем только основной подход.
Начинается вставка с поиска пути по дереву к ключу k, который надо вставить. Алгоритм практически идентичен алгоритму поиска пути, только нас интересует лишь путь S, получающийся в результате. Кроме того, нам понадобятся три дополнительные строки, получаемые из найденного пути и строки k: common, rest и key. Строятся они следующим образом. Возьмём строку s, которая получилась из строки, соответствующей найденному пути S удалением последнего префикса. Она, очевидно, является префиксом добавляемой строки k (либо совпадает с ней). Будем рассматривать строку k, которая получилась из k удалением этого префикса s. Тогда common — это наибольший общий префикс строк k и p=prefix(S[n]) (где S[n] — последняя вершина пути S). rest — это остаток от строки p, полученный удалением префикса common, и key — остаток от k, полученный удалением префикса common. Все три строки удобно считать одновременно, и их значение иллюстрирует следующая схема:
Алгоритм вставки рассматривает пять случаев:
- В дереве нет узлов. В этом случае нам надо выделить страницу, на которой расположить единственный новый узел дерева.
- rest и key — пустые строки. В этом случае нам достаточно пометить последнюю вершину пути как final (в случае минимального дерева она уже будет помечена как final).
- key — пустая строка, rest — непустая. В этом случае нам достаточно разбить последнюю вершину пути на две, одна их которых будет содержать префикс common и будет помечена как final.
- key — непустая строка, rest — пустая.
В этом случае нам надо добавить дополнительную вершину с префиксом key, дочернюю по отношению к последней вершине пути. - key и rest — суть непустые строки. В этом случае последняя вершина xn разбивается на три: одну с префиксом common, с двумя исходящими из неё — xn, префиксом которой становится rest, и final-вершину с префиксом key.
Основной момент, который связан с разделением на блоки, заключается в том, что в случае 4 и 5 если ветка, в которую мы производим добавление, имеет дочерние ветки, мы создаём новую вершину с key в новой ветке. Для этого мы находим среди дочерних веток ту, на странице которой осталось больше всего места. Это самая дорогая из всех приведённых операций, т.к. требует в худшем случае чтение такого количества страниц, которое равно количеству различных возможных дочерних веток. На практике это неприемлемо. Поэтому в нашей реализации мы ограничеваем количество просматриваемых страниц некоторой константой D (в реализации равна 2). В случае, если среди первых просмотренных D страниц не нашлось той, в которую помещается добавляемая вершина, пытаемся расширить самую занятую из просмотренных. При таком подходе затрагивается не более D+2 страниц.
