Использование индексов (индексирование)

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

Для того чтобы использовать дихотомический поиск и не перемещать физические записи при добавлении новых записей, используется так называемое логическое упорядочение физических записей (индексирование). Основная структура хранения содержит записи исходной таблицы и представлена в виде неупорядоченной последовательности физических записей. Для возможной реализации дихотомического поиска по определенному ключу создается дополнительная структура хранения (так называемый индекс). Число записей в индексе равно числу записей исходной таблицы (числу физических записей в основной структуре хранения). Каждая запись индекса имеет два поля: ключевое поле записи основной структуры и указатель – адрес записи основной структуры с соответствующим значением ключа.

Записи индекса (индексного файла) упорядочены по значению ключа. Адреса связи этих записей определяют логическое упорядочение записей основной структуры хранения.

Пример соответствующей структуры хранения приводится в предположении k=1на рис. 14.

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

Рис. 9.6. Индексирование

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

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