Включение: добавить запись с ключом v1

Модификация: аналогично предыдущей.

Поиск: найти запись с ключом v1.

Инициализация: процедура формирования файла индекса по первоначальному главному файлу называется – инициализацией.

Организация сортированных файлов с закрепленными записями.

Если записи закреплены (пояснить), то не возможно (вообще говоря) поддерживать их внутри блока в отсортированном порядке. Нет возможности даже гарантировать, что записи предыдущего блока предшествуют записям последующего блока (относительно некоторого ключа).

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

Рассмотрим операции над таким файлом.

Для инициализации отсортируем файл и распределим его записи по блокам. При этом в каждом блоке выделим некоторое свободное пространство (несколько свободных субблоков) которые при добавлении записи исключат на некоторое время рост цепочек в участках главного файла. Кроме того, предусмотрим один пустой блок в участке, предшествующем первому, куда будем помещать записи при расширении файла, и которые будут предшествовать записям первоначального файла. Создадим индекс для полученного файла, в том числе и для пустого блока. Запись в индексе для этого блока должна содержать номер «пустого» блока и не содержать ключа.

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

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

Удаление: поиск записи с ключом v₁. Если запись найдена, то установка бита удален в состояние «1» (запись удалена). Если данная запись не закреплена установка бита свободен/занят в состояние свободен.

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