Базы данных. Вводный курс


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


Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева. Тип дерева состоит из одного «корневого» типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.

На рис. 2.1 показан пример типа дерева (схемы иерархической БД). Здесь тип записи Отдел

является предком для типов записи Руководитель

и Служащие, а Руководитель

и Служащие

– потомки типа записи Отдел. Смысл полей типов записей в основном должен быть понятен по их именам. Поле Рук_Отдел

типа записи Руководитель

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

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


Рис. 2.1. Пример типа дерева

База данных с такой схемой могла бы выглядеть так, как показано на рис. 2.2 (мы показываем один экземпляр дерева).


Рис. 2.2. Пример иерархической базы данных

Все экземпляры данного типа потомка с общим экземпляром типа предка называются близнецами. Для иерархической базы данных определяется полный порядок обхода дерева: сверху-вниз, слева-направо. Заметим, что в терминологии IMS вместо термина запись

использовался термин сегмент, а под записью базы данных понималось все дерево сегментов.




Начало  Назад  Вперед