4.2.1. Физически последовательное размещение

 

На рис. 4.7 и рис. 4.8 представлен пример реализации иерархической структуры до и после обновления путем физически последовательного размещения данных на носителе.

 

 

Рис. 4.7. Пример реализации древовидной структуры до обновления

 

 

Рис. 4.8. Пример реализации древовидной структуры после обновления

 

Последовательность элементов на рис. 4.7 иногда называется левосписковой структурой (по­следовательность типа «сверху вниз - слева направо»).

Последовательность строится следующим образом: выбираются узлы, начиная от вершины дерева и вниз по самой левой ветви дерева; когда выбран узел самого нижнего уровня этой ветви, выбираются по­добные узлы слева направо; процесс повторяется, причем уже выбранные узлы пропускаются.

При размещении каждой записи последовательности в памяти мо­жет указываться, к какому уровню дерева она относится. Это выпол­няется путем введения в каждую запись специального кода (на­пример, тип записи может быть определен по типу ключа). Возможно также использование некоторой формы разграничения последовательности записей, например представление записи в таком виде:

A1(B2(C5C12C6)B1(C12C9)B3(C14C11C7C18))

Последовательные левосписковые структуры не позволяют осу­ществлять быстрый выбор элементов нижних уровней дерева, так как при этом требуется просмотр всего списка.

 

 

К оглавлению

Назад к разделу "4.2. Физическое представление иерархических структур"

Вперед к разделу "4.2.2. Левосписковые структуры с переполнениями"