Модификация

Поиск.

Задача: найти запись со значением ключа v.

Алгоритм поиска пути от корня В–дерева к некоторому листу, в котором будет находится требуемая запись, если она существует. (рекурсивный алгоритм).

a) начало поиска от корня дерева. Устанавливаем текущий уровень дерева =1.

b) пусть рассматривается узел дерева с номером «i». Возможны две ситуации:

- i – лист (это легко проверяется подсчетом текущего уровня дерева от корня и сравнением этой величины полной длинной дерева). В этом случае проверим находится ли запись с ключом v в данном блоке (главного файла). Если да – успех, если нет – записи нет, конец алгоритма;

- i – не лист, следовательно, i → блок индекса. Определим, какое значение ключа в блоке В покрывает v (учитывая, что первая запись блока не содержит ключа и первое значение покрывает все значения ключей, меньших значения ключа во второй записи).

В блоке «i» для значения ключа, которое покрывает ключ v находим указатель на другой блок.

c) увеличиваем текущий уровень дерева на 1 и повторяем данный алгоритм с пункта b) для нового блока.

После поиска обработка ситуации:

a)нет записи;

b) хотя бы одно поле входит в ключ (запись удаляется из внешней памяти в оперативную память, где она модифицируется, а потом снова записывается в внешнюю память).

Включение.

Включить запись с ключом v.

a) найти блок «i», к которому эта запись относится, если запись есть в блоке «i», то аварийный останов;

b) в блоке i нет записи с ключом V:

- если в блоке меньше, чем 2е-1 запись, то запись просто включается в блок в отсортированном порядке. Эта запись некогда не может быть самой левой в блоке, если только блок «i» не является самым левым листом, т.е. нет необходимости изменять предшественника блока «i» (в индексе). Но в этом случае предшественник по уровню не корректируется, т.к. первая запись блока индекса не имеет ключа;

- если в блоке 2е-1 записи (нет места) то создадим новый блок «i₁». Разделим записи этого блока с добавляемой, между двумя блоками «i» и «i₁», по «е» записей (было 2е-1 и добавляем 1 =2е).

Пусть теперь «j» - отец блока «i» (j- известен, т.к. при поиске мы построили путь от корня к «i»). Применим данную процедуру включения к блоку «j» рекурсивно, но с константой d (в блок «j» добавлена запись о блоке «i₁»). Если многие предки блока «i» заполнены полностью (по 2d-1 записей), то процедура расширения распространяется на несколько уровней и может достигнуть корня дерева. Если и он заполнен полностью, то его необходимо расщепить на два блока и получив у OS еще один блок создать новый корень, в котором будет две записи (т.о. размер дерева увеличится на единицу). При этом в корне в корне может быть меньше d записей (если 2d-1>3).

Дата добавления: 2014-01-05