Неплотный индекс

Пусть основной файл

упорядочен по полю ключа

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

(рис. 3.9) по правилу [17]:

имеют формат

, где

-поле, принимающее значение ключа первой записи блока основного файла

;

– указатель на этот блок;

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

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

. Полученный файл

называется неплотным индексом. Количество записей файла

равно количеству блоков основного файла

. Для организации файла

требуется дополнительная внешняя память.

, где

– количество записей в блоке индекса. Такое дерево должно иметь в каждом узле не менее

зависимых узлов и все листья должны располагаться на одном уровне.

Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа. Поиск в В-дереве выполняется так же, как и в неплотном индексе. Удачный и неудачный поиск записи в В-дереве требует

обменов, где

– число уровней В-дерева.

При поиске по интервалу значений

вначале выполняется поиск по

в В-дереве, а затем – последовательный поиск по условию

в блоках 1-го уровня В-дерева.

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