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

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

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

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

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

A1(132(C5C12C6) В1(С12С9) B3(C14C11C7C18) )

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