Информационное обеспечение систем управления

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


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

 упорядочен по полю ключа
. Построим дополнительный файл
 (рис. 3.9) по правилу [17]:

 имеют формат
, где
 -поле, принимающее значение ключа первой записи блока основного файла
;
 – указатель на этот блок;

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

 упорядочены по полю
. Полученный файл
 называется неплотным индексом. Количество записей файла
 равно количеству блоков основного файла
. Для организации файла
 требуется дополнительная внешняя память.

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

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

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

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

 вначале выполняется поиск по
 в В-дереве, а затем – последовательный поиск по условию
в блоках 1-го уровня В-дерева.



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