Основные положения индексации

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

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

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

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

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

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

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