Индексированные файлы.

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

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

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

Дополнитнльный индексный файл называется внешним индексом, а исходный файл – индексированным.

Использование внешнего индекса имеет три условия:

1) нужно знать заранее критерии, по которым будет производиться поиск: для каждого критерия строится индексный файл;

2) ссылки на все добавления в исходный файл должны помещаться в соответствующие места индексных файлов, чтобы не нарушать их упорядоченность;

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