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

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

, упорядоченный либо неупорядоченный по значениям вторичного ключа

. Строится дополнительный файл

по правилу [17]:

1) записи файла

имеют формат

где

- поле, принимающее значение вторичного ключа

записи основного файла;

– указатели на записи основного файла

, имеющие данное значение вторичного ключа

2) записи файла

, упорядочены по полю

Построенный дополнительный файл

. называется инвертированным. В этом случае об основном файле

говорят, что он инвертирован по полю

. Количество записей в инвертированном файле

определяется количеством значений вторичного ключа

в записях основного файла

. Пример инвертированного файла по полю

для основного файла

приведен на рис. 3.12.

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

. Если фиксированного числа поле для некоторых записей окажется недостаточно, то организуется еще дополнительный служебный файл для хранения неуместившихся цепочек указателей.

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

ключам, необходимо построить

инвертированных файлов [17].

Содержание раздела