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

Рассмотрим физическое представление древовидных структур (см. гл. 2, разд. 2.1) на примере обновления дерева с использованием следующих методов:

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

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

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

Рис. 1.28. Пример древовидной структуры

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

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

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

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

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