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

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

Основные понятия

В иерархической модели данные представляются как совокупность узлов (также называемых сегментами, записями или элементами), соединённых направленными связями «родитель — потомок». Каждый узел содержит набор полей (атрибутов), описывающих его свойства. Структура в целом соответствует математическому понятию дерева.

Определяющие характеристики:

• Корень дерева — единственный узел, не имеющий родителя.
• Родительский узел — узел, от которого исходят связи к подчинённым узлам.
• Дочерние узлы — узлы, подчинённые данному родителю.
• Лист — узел, не имеющий потомков.
• Путь — последовательность узлов от корня до данного узла, определяющая его адрес в иерархии.
• Уровень иерархии — расстояние от корневого узла, измеряемое количеством связей.

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

История и развитие

Иерархическая модель данных была разработана в середине 1960-х годов, главным образом в рамках проекта IBM Information Management System (IMS). IMS, созданный для программы «Аполлон» (NASA), стал одной из первых коммерчески успешных СУБД. Модель основывалась на навигационном подходе к доступу к данным, где программист вручную перемещался по дереву с помощью специальных команд.

В 1971 году Конференция по языкам систем данных (CODASYL) предложила альтернативную сетевую модель, более гибкую, но и более сложную. Тем не менее, иерархические системы доминировали в мейнфреймовом мире до середины 1980-х годов, пока их не начали вытеснять реляционные СУБД (например, IBM DB2, Oracle). Реляционная модель, основанная на математической теории множеств, предложила большую гибкость, независимость данных и удобство работы через язык запросов SQL.

Однако иерархическая модель не исчезла полностью. Она получила «второе рождение» с распространением языка разметки XML и технологии LDAP, а также остаётся естественным способом представления таких данных, как каталоги товаров, организационные структуры, генеалогические деревья и файловые системы.

Организация данных

В иерархической СУБД типы узлов определяются схемой базы данных. Для каждого типа задаётся набор полей (например, для типа «Сотрудник»: фамилия, должность, зарплата) и правила подчинённости (какие типы могут быть потомками данного типа). Схема описывается в терминах «сегментов» и «связей».

Пример простейшей иерархии для отдела кадров:

• Отдел (название, номер)
• Сотрудник (фамилия, должность, дата найма)
• Проект (название, дата начала)

Здесь «Отдел» — корневой сегмент, «Сотрудник» — дочерний по отношению к «Отделу», а «Проект» — дочерний по отношению к «Сотруднику». Каждый конкретный экземпляр отдела может содержать нескольких сотрудников, а каждый сотрудник — несколько проектов. Однако один и тот же проект не может принадлежать двум разным сотрудникам (если только не использована избыточность или не введён дополнительный уровень иерархии).

Физически данные хранятся в виде последовательностей записей, связанных указателями. Распространены две схемы хранения:

• Иерархическая с последовательным расположением (HSAM — Hierarchical Sequential Access Method) — записи хранятся в порядке обхода дерева (например, сверху вниз, слева направо).
• Иерархическая с индексами и указателями (HDAM/HIDAM — Hierarchical Direct/Indexed Direct Access Method) — для быстрого доступа используются индексы и цепочки указателей.

Операции над данными

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

• GET UNIQUE (GU) — поиск первой записи, удовлетворяющей заданным условиям по ключу или по пути.
• GET NEXT (GN) — переход к следующей записи того же типа в последовательности обхода.
• GET NEXT WITHIN PARENT (GNP) — переход к следующей дочерней записи в рамках текущего родителя.
• INSERT — добавление новой записи в дерево (необходимо указать родителя).
• DELETE — удаление записи вместе со всеми её потомками (каскадное удаление).
• REPLACE (UPDATE) — обновление полей текущей записи.

Поиск данных требует указания полного пути от корня к искомой записи. Например, чтобы найти сотрудника с табельным номером 123 в отделе «Продажи», необходимо сначала установить курсор на отдел «Продажи», затем среди его дочерних записей найти сотрудника с нужным номером. Такой способ доступа называют навигационным.

Языки обработки данных в иерархических СУБД (DL/I для IMS, DL/1 для DLI) были процедурными, то есть программист должен был явно описывать последовательность переходов по дереву. Это делало разработку сложных запросов трудоёмкой, особенно по сравнению с декларативным SQL.

Достоинства и недостатки

Достоинства:

• Естественность представления для многих реальных сущностей (организационные структуры, каталоги, таксономии).
• Высокая производительность при работе с предопределёнными иерархическими запросами благодаря минимуму операций соединения (join) и оптимизированному последовательному доступу.
• Целостность ссылок — невозможность «сиротских» записей без родителя (каждая запись, кроме корня, обязательно принадлежит родителю).
• Простота понимания на концептуальном уровне.

Недостатки:

• Ограниченная гибкость — невозможность представить отношения «многие ко многим» без избыточного дублирования данных (например, сотрудник, участвующий в нескольких проектах, должен быть либо продублирован в разных ветвях, либо проекты должны быть подчинены другому узлу, что нарушает естественную связь).
• Зависимость от иерархии — добавление нового типа данных или изменение структуры (например, перенос сотрудника в другой отдел) может потребовать перестройки всей базы даных или привести к потере производительности.
• Трудность выполнения произвольных запросов — любой запрос, не соответствующий заранее заданному пути (например, «найти всех сотрудников с зарплатой выше 100 000»), требует полного обхода дерева.
• Отсутствие стандартизации — разные СУБД реализуют иерархическую модель с существенными различиями в синтаксисе и возможностях.

Сравнение с другими моделями

Иерархическая модель исторически предшествовала сетевой и реляционной. Основные отличия:

Современное применение

Несмотря на доминирование реляционных и NoSQL СУБД, иерархическая модель остаётся востребованной в ряде областей:

• Файловые системы — каждая операционная система использует древовидную структуру директорий (папок) и файлов (с вариациями, например, символические ссылки нарушают строгую иерархию).
• LDAP-каталоги — протокол Lightweight Directory Access Protocol оперирует иерархическим деревом записей (например, домены, организационные единицы, пользователи).
• XML-документы — язык разметки XML полностью описывает иерархическую структуру вложенных элементов; для обработки XML применяются XPath и XSLT, основанные на навигации по дереву.
• Системы управления контентом (CMS) — таксономии и рубрикаторы сайтов часто строятся как иерархии (например, категории товаров).
• Географические информационные системы (ГИС) — административно-территориальное деление стран имеет естественную иерархию (страна → регион → район → населённый пункт).
• СУБД IMS — активно используется в банковском секторе и крупных корпоративных системах (до сих пор обслуживается и развивается компанией IBM).

Интересные факты

• Система IMS компании IBM, созданная в 1968 году, до сих пор остаётся одной из самых производительных транзакционных СУБД в мире, обрабатывая миллиарды транзакций в день в таких отраслях, как банкинг, авиаперевозки и страхование.
• Многие современные базы данных NoSQL, такие как MongoDB, предоставляют средства для работы с иерархическими документами (JSON-деревья), что можно рассматривать как возврат к идеям иерархической модели, но с более гибкой схемой.
• В 1970 году Тед Кодд опубликовал свою знаменитую статью «A Relational Model of Data for Large Shared Data Banks», которая положила начало реляционной эре, во многом как реакция на недостатки иерархической модели.