Введение в информационные системы. Брюхомицкий Ю.А. - 132 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

132
Таблица 10.1
Число
уровней
Размер
блока
Занимаемая справоч-
ником память
Среднее число
обращений
0 0 0 500 000
1 N=1 000 1 000 1 000
2
3
N= 100 10 000 150
3
4
N= 31 33 000 63
4
5
N= 16 66 000 40
5
6
N= 10 100 000 30
Справочник, основанный на структуре сбалансированного дерева.
Трудности, связанные с ведением многоуровневого справочника, уменьшаются,
если для его организации использовано связанное представление данных. Мно-
гоуровневый справочник строится при этом по принципу наращиваемого сба-
лансированного дерева, называемого также В-деревом. Структура В-дерева
обеспечивает высокую скорость выполнения процедур поиска и ведения для
больших
информационных массивов, хранящихся во внешней памяти. Спра-
вочник, организованный по принципу В-дерева, называют индексом, а уровни
справочника − уровнями индекса.
Каждая вершина древовидного справочника представлена блоком из m
ячеек памяти. В каждой ячейке размещается справочная запись, состоящая из
поля ключа и поля указателя. Указатель связывает каждую ячейку блока
с по-
рожденным блоком ближайшего нижнего уровня.
Верхний (первый) уровень индекса делит весь диапазон возможных
значений ключа на m крупных интервалов. Каждая ячейка первого уровня свя-
зана с блоком ячеек второго уровня индекса, каждая ячейка каждого блока вто-
рого уровня связана с блоком ячеек третьего уровня индекса и т.д. Последняя
ячейка
каждого блока содержит значение ключа порождающей ячейки. Блок
каждого уровня, лежащего ниже, делит соответствующий диапазон значений
ключа на m более мелких интервалов. Ячейки самого нижнего уровня связаны
указателями с записями основного массива. Все уровни индекса упорядочены
по возрастанию значений ключа. На рис. 10.4 изображено дерево трехуровнево-
го справочника для упорядоченного основного массива,
записи которого имеют
диапазон значений ключа от 7 до 178.
В структуре сбалансированного дерева, незаполненным может быть
только самый нижний его уровень, и новый уровень индекса можно образовы-
вать, если все блоки нижнего уровня будут полностью заполненными.
Поиск записи с определенным значением ключа начинается с просмот-
ра верхнего уровня индекса. В блоке индекса
ищется значение ключа, большее
или равное искомому, причем предыдущая запись блока должна иметь меньший
ключ. От найденной записи по указателю спускаются в порожденный блок вто-
рого уровня индекса и в нем отыскивают запись с большим или равным иско-

Страницы