Ключ – значение (элемент данных), используемое для идентификации или определения адреса записи. (логическое определение).
Ключ сцепленный (составной) – несколько элементов данных, которые в совокупности обеспечивают уникальность идентификации каждой записи набора данных.
Индекс – физическая реализация ключа, обеспечивающая доступ к записям, соответствующим отдельным значениям ключа.
Логически индекс есть бинарное отношение I(v,a), где v – значение атрибута, а a – список адресов элементов хранения (записей, кортежей, документов), соответствующих данному значению атрибута. Для повышения эффективности поиска отдельных значений и слияния/пересечения списков значения v и адреса элементов в списке a хранятся в упорядоченном виде, что обеспечивает применение процедур быстрого поиска.
Индекс I(v,a) часто называют инвертированным индексом. Каждый элемент а инвертированного индекса наз. инвертированным списком.
Прямая реализация индекса представляет собой расширение бинарного отношения до совокупности записей, состоящих из 2-ух полей – значения атрибута и адреса размещения одного элемента хранения. Отдельное значение атрибута повторяется в индексе столько раз, сколько оно встречается в файле данных, а длина индекса (в записях) совпадает с длиной файла данных.
В инвертированной форме:
В случае, когда списки а достаточно длинные, инвертированный индекс хранится в двух разных файлах, связанных указателями. Такая организация требует меньше памяти для хранения значений ключей и поиск в ней более эффективен.
Способы реализации указателя пересылок:

- Указанием ссылки на первый и последний адреса размещения элементов для отдельного ключевого значения;
- Заданием ссылки на адрес размещения первого элемента и длиной списка адресов.

 

Пример: