Индексно-произвольный способ

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

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

Пример 8. Организуем индексно-произвольный доступ к линейному списку из таблицы 5, обеспечив индексно-последовательный доступ по ключу Фамилия.

Тогда построим дополнительный индекс, показанный в таблице 7:

Таблица 7

Поскольку таблица 7 – не что иное, как упорядоченный линейный список, к нему как к самостоятельному линейному списку применимы все методы доступа, рассмотренные ранее.

Таким образом, решение задачи включает три линейных списка, представленные в таблицах 5, 6, 7.