Пусть по каким-либо причинам невозможно упорядочить основной файл
по ключу
. Построим дополнительный файл
по правилу [17]:
1) записи файла
имеют формат
, где
– поле, принимающее значение ключа записи основного Файла
;
– указатель на эту запись;
2) записи файла
упорядочены по полю
. Полученный файл называется плотным индексом. Он строится почти так же, как и неплотный индекс. Различие заключается в том, что для каждого значения ключа
в файле
имеется отдельная запись, а в неполном индексе – только для значения ключа пер. вой записи блока.
Пример плотного индекса представлен на рис. 3.11. Над плотным индексом можно также построить В-дерево.
