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

UptoLike

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

Рубрика:

131

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

справочник называется многоуровневым. В результате увеличения числа уров-

ней уменьшается количество последовательно просматриваемых записей, так

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

Однако объем памяти под справочник при этом увеличивается.

Поиск в многоуровневом справочнике начинается с просмотра верхнего

уровня, затем

следует обращение по указателю и просмотр ближайшего низше-

го уровня до тех пор, пока не будет найден блок основного массива, которому

должна принадлежать искомая запись.

В процессе ведения основного массива при включении и удалении за-

писей многоуровневый справочник подлежит корректировке на всех уровнях

так, как это было описано выше.

Эффективное ведение

поиска в многоуровневых справочниках обеспе-

чивается определенными соотношениями между размером основного массива,

числом уровней и размером блока. В табл. 10.1 приведены соответствующие

данные для многоуровневых справочников, основной массив которых содержит

1000000 записей.

Справочник Справочник Основной

второго уровня первого уровня массив

Рис. 10.3. Принцип построения двухуровневого справочника