Рис. 3.11. Пример плотного индекса

3.3.6.Инвертированный файл

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

значениям вторичного ключа Кi. Строится дополнительный файл FDi по правилу [17]:

1)записи файла FDi имеют формат FDi(Ki, P) где Ki – поле, принимающее значение вторичного ключа Кi записи основного файла; Р – указатели на записи основного файла F, имеющие данное значение вторичного ключа Кi;

2)записи файла FDi упорядочены по полю Ki.

Построенный дополнительный файл FD. Называется инвертированным. В этом случае об основном файле F говорят, что он инвертирован по полю Кi. Количество записей в инвертированном файле FDi определяется количеством значений вторичного ключа Кi в записях основного файла F. Пример инвертированного файла по полю К2 для основного файла F приведен на рис. 3.12. Рассмотренный способ организации инвертированного файла предполагает использование записей переменной длины. Инвертированный файл можно организовать и с помощью записей фиксированной длины, если в каждой записи инвертированного файла выделять фиксированное число полей для указателей Р. Если фиксированного числа поле для некоторых записей окажется недостаточно, то организуется еще дополнительный служебный файл для хранения неуместившихся цепочек указателей.

82