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

Такая организация основана на понятии уникального ключа. Основная особенность этих файлов в никогда не нарушаемой последовательности записей.

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

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

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

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

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

Обычно при организации индексированного файла каждый блок оставляют пустым на 20% для того, чтобы повысить эф-ть добавления записи (стремимся как можно реже вносить изменения в индекс).

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

Инициализация. Есть записи с ключами 16, 2, 5, 37, 79, 56, 4, 25, 54, 68.

Процесс состоит из трех этапов.

1-ый этап. Сортируем записи в исходном файле и сортируем по блокам. Обычно файлы БД имеют тенденцию к увеличению, поэтому при создании блоки оставляют свободными на 20 %. После 1-го этапа главный файл имеет вид упорядоченных записей, размещенных в упорядоченные блоки.

2-ой этап. Создание индексного файла. При этом берутся первые элементы каждого блока и создаются пары (значение ключа, адрес блока). Исключение составляет первый блок. Для него пара (-∞,B) – это необходимо для работы со значениями меньше всех существующих в файле.

3-ий этап. Организация блоков индексного файла. Будем считать, что индексный файл организован в виде последовательности.

Алгоритм поиска заключается в следующем. Пусть ищем запись со значением ключа v₁, тогда в индексе необходимо найти пару (v₂, b) такую, что v₂ ≤ v₁ и либо v₂ последняя запись индекса, либо последующие записи имеют вид (v₃, b), где v₃ > v₁. Искомая запись гарантированно нах-ся в блоке, адрес к-ого принадлежит паре (v₂, b). В этом случае говорят, что v₂ покрывает v₁. Т.о., эффективность поиска равна эффективности поиска в индексе + одно обращение к главному файлу. Поиск в индексе м.б. линейным, двоичным и интерполирующим.