Плотный индекс

Пусть по каким-либо причинам невозможно упорядочить основной файл

по ключу

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

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

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

имеют формат

, где

– поле, принимающее значение ключа записи основного Файла

;

– указатель на эту запись;

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

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

. Полученный файл называется плотным индексом. Он строится почти так же, как и неплотный индекс. Различие заключается в том, что для каждого значения ключа

в файле

имеется отдельная запись, а в неполном индексе – только для значения ключа пер. вой записи блока.

Пример плотного индекса представлен на рис. 3.11. Над плотным индексом можно также построить В-дерево.

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

Содержание Назад Вперед