Манипулирование данными

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

Иерархическая модель данных

Типичным представителем (наиболее известным и распространенным) является СУБД IMS (Information Management System) компании IBM. Первая версия системы появилась в 1968 г.

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

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

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

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

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

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

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

• найти указанный экземпляр типа дерева БД (например, отдел 310);
• перейти от одного экземпляра типа дерева к другому;
• перейти от экземпляра одного типа записи к экземпляру другого типа записи внутри дерева (например, перейти от отдела к первому сотруднику);
• перейти от одной записи к другой в порядке обхода иерархии;
• вставить новую запись в указанную позицию;
• удалить текущую запись.