Индексированные файлы: операции вставки и удаления записей

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

Разреженные индексы

В разреженном индексе ключ должен гарантировать уникальное значение. Записи индекса состоят из пар (v, b), где b – адрес блока, а v – зн-ние ключа 1ой записи блока. Записи в главном файле д.б. упорядочены. Записи в индексе также упорядочены.

Плотное индексирование

Плотные индексы не требуют упорядочивать гл. файл и не требуют уникальности ключа, поэтому для нек-ого отношения можно построить мн-во плотных индексов. Запись в плотном индексе представляет собой пару (V, p), где V – зн-ние ключа записи, а p – адрес записи.

В файле индекса в самой 1ой записи вместо значения ключа помещается -∞, чтобы упростить алгоритм поиска. Индекс также может состоять более чем из одного блока. В этом случае блоки индекса организуются как последовательный файл, либо над индексом строится еще один индекс.

Для разреженных индексов

Операция вставки

Пусть необходимо добавить запись с ключом v₁. Для этого необходимо найти блок b_i, в к-ом д.б. запись. Затем объясняем корректное положение записи в блоке b_i. Для этого смещаем все записи с ключом большим v₁ вправо. Если блок b_i не содержит свободного места, то выделяется новый блок в главном файле, записи распределяются пополам между b_i и новым блоком (порядок д.б. сохранен). При появлении нового блока инфо о нем д.б. записана в индексном файле. При этом также должен сохраняться порядок записей.

Операция удаления

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