Классика баз данных - статьи

       

Вставка


Процедура добавления строки устроена таким образом, что она сначала строит структуру, описывающую изменение страницы, в которую надо вставить новые вершины. Может случиться, что для вставки нет места в странице. В этом случае процедура вызывает расширение дерева на необходимую величину, и вставка не происходит. Она должна быть вызвана ещё раз. Заметим также, что корень дерева может измениться в процессе работы процедуры.

Сама процедура добавления достаточно проста, однако она слишком велика, чтобы приводить её здесь. Опишем только основной подход.

Начинается вставка с поиска пути по дереву к ключу 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. Все три строки удобно считать одновременно, и их значение иллюстрирует следующая схема:

Алгоритм вставки рассматривает пять случаев:

  1. В дереве нет узлов. В этом случае нам надо выделить страницу, на которой расположить единственный новый узел дерева.
  2. rest и key — пустые строки. В этом случае нам достаточно пометить последнюю вершину пути как final (в случае минимального дерева она уже будет помечена как final).
  3. key — пустая строка, rest — непустая. В этом случае нам достаточно разбить последнюю вершину пути на две, одна их которых будет содержать префикс common и будет помечена как final.
  4. key — непустая строка, rest — пустая.
    В этом случае нам надо добавить дополнительную вершину с префиксом key, дочернюю по отношению к последней вершине пути.
  5. key и rest — суть непустые строки. В этом случае последняя вершина xn разбивается на три: одну с префиксом common, с двумя исходящими из неё — xn, префиксом которой становится rest, и final-вершину с префиксом key.


Основной момент, который связан с разделением на блоки, заключается в том, что в случае 4 и 5 если ветка, в которую мы производим добавление, имеет дочерние ветки, мы создаём новую вершину с key в новой ветке. Для этого мы находим среди дочерних веток ту, на странице которой осталось больше всего места. Это самая дорогая из всех приведённых операций, т.к. требует в худшем случае чтение такого количества страниц, которое равно количеству различных возможных дочерних веток. На практике это неприемлемо. Поэтому в нашей реализации мы ограничеваем количество просматриваемых страниц некоторой константой D (в реализации равна 2). В случае, если среди первых просмотренных D страниц не нашлось той, в которую помещается добавляемая вершина, пытаемся расширить самую занятую из просмотренных. При таком подходе затрагивается не более D+2 страниц.


Содержание раздела