Пример,. Операции над индексированными файлами

Операции над индексированными файлами

Инициализация. Пусть имеются записи со следующими значениями ключей: 16, 2, 5, 37, 79, 56, 4, 25, 54, 68

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

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

Пусть в блок вмещается по пять записей, тогда схема организации основного файла будет иметь вид представленный на рисунке 8.

Рисунок 8 – Организация основного файла

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

Рисунок 9 – Организация индексного файла

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

Дата добавления: 2015-05-09