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

       

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


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

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

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

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

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

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

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

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

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

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



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