Поиск информации. Индексные файлы

Допустим, мы работаем с системой КАДРЫ и хотим найти зарплату для сотрудника с табельным номером N. Простейший метод- чтение всех записей до того как найдем N. Во многих случаях метод перебора не устраивает. При наличии очереди клиентов (касса аэропорта, оптовый склад) выполнение запроса по десяткам тысяч записей должно занимать единицы секунд.

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

Теперь усложним задачу и зададим следующий вопрос: «Перечислить сотрудников отдела В с зарплатой менее 80000 рублей». В этом случае придется сначала упорядочить таблицу по коду отдела, но тогда нарушится упорядочение по табельному номеру и по нему - опять придем к медленному варианту поиска - перебору.

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

Для каждой таблицы можно создать любое нужное количество индексных файлов. При этом она называется индексированной.

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

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

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