Базы данных. Вводный курс
Иерархические структуры данных
Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева. Тип дерева состоит из одного «корневого» типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.
На рис. 2.1 показан пример типа дерева (схемы иерархической БД). Здесь тип записи Отдел
является предком для типов записи Руководитель
и Служащие, а Руководитель
и Служащие
– потомки типа записи Отдел. Смысл полей типов записей в основном должен быть понятен по их именам. Поле Рук_Отдел
типа записи Руководитель
содержит номер отдела, в котором работает служащий, являющийся данным руководителем (предполагается, что он работает не обязательно в том же отделе, которым руководит). Между типами записи поддерживаются связи (правильнее сказать, типы
связей, поскольку реальные связи появляются в экземплярах типа дерева).
Рис. 2.1. Пример типа дерева
База данных с такой схемой могла бы выглядеть так, как показано на рис. 2.2 (мы показываем один экземпляр дерева).
Рис. 2.2. Пример иерархической базы данных
Все экземпляры данного типа потомка с общим экземпляром типа предка называются близнецами. Для иерархической базы данных определяется полный порядок обхода дерева: сверху-вниз, слева-направо. Заметим, что в терминологии IMS вместо термина запись
использовался термин сегмент, а под записью базы данных понималось все дерево сегментов.
