Неплотный индекс
Пусть основной файл
упорядочен по полю ключа
. Построим дополнительный файл
(рис. 3.9) по правилу [17]:
имеют формат
, где
-поле, принимающее значение ключа первой записи блока основного файла
;
– указатель на этот блок;
2) записи файла
упорядочены по полю
. Полученный файл
называется неплотным индексом. Количество записей файла
равно количеству блоков основного файла
. Для организации файла
требуется дополнительная внешняя память.
, где
– количество записей в блоке индекса. Такое дерево должно иметь в каждом узле не менее
зависимых узлов и все листья должны располагаться на одном уровне.
Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа. Поиск в В-дереве выполняется так же, как и в неплотном индексе. Удачный и неудачный поиск записи в В-дереве требует
обменов, где
– число уровней В-дерева.
При поиске по интервалу значений
вначале выполняется поиск по
в В-дереве, а затем – последовательный поиск по условию
в блоках 1-го уровня В-дерева.
Содержание Назад Вперед
