Индексно-последовательный метод

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

Поиск производится следующим образом. В оперативную память загружается индекс, в нем выбирается ссылка на диапазон ключей, в котором предположительно находится искомая запись. Затем в память загружается нужный блок, в нем последовательным методом ищется нужный ключ.

Неплотность индекса дает возможность уменьшить количество его записей по сравнению с объемом базы кратно размеру блока. Но индекс все равно может стать слишком большим и не помещаться в память. Тогда есть два пути: либо увеличить блок, либо как-то реорганизовать индекс. Блок увеличить можно лишь в ограниченных пределах: во-первых, он должен помещаться в память, во-вторых – поиск в нем ключа не должен заметно сказываться на производительности. С индексом можно поступить интереснее: его можно рассматривать как информационный файл и, в свою очередь, проиндексировать. Таким образом, получается иерархия индексов, каждый элемент которой способен разместиться в память. Начальную загрузку для этого метода делают из сортированного файла.

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

Эффективность доступа зависит от размера индексов и числа уровней их иерархии. Кроме того, на нее влияет размер блоков, наличие в них свободных мест, наличие областей переполнения.

Эффективность хранения в основном зависит от объема свободного места в блоках и от величины индексов.

Пример

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