Иерархические структуры данных

Иерархическая модель данных (ИМД) свойственна многим реальным древовидным структурам (классификаторы, структуры управления и т. п.). Существуют графовая и табличная формы представления данных ИМД. Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева. Дерево - связный неориентированный граф, который не содержит циклов.

Иерархическая древовидная структура, ориентированная от корня (выделенная вершина или узел) определяется условиями:

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

· на нижних уровнях находятся порожденные (зависимые) узлы;

· каждый порожденный узел, находящийся на і-том уровне, связан непосредственно с одним исходным (родительским) узлом, находящимся на (і-1) уровне иерархии;

· каждый исходный узел может иметь один или несколько непосредственно порожденных узлов;

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

· существует единственный иерархический путь доступа к узлу, начиная от корня дерева (рис. 2. 2).

Иерархический путь включает в себя все связанные между собой узлы.

В ИМД используется ориентация древовидной структуры от корня к листьям дерева. Пример схемы иерархической БД представлен на рис 2. 3.

 

Рисунок 2.2 Пример иерархической структуры.

Для БД определен полный порядок обхода – «сверху-вниз», «слева-направо».

Рисунок 2.3 Иерархическая БД