Иерархическая база данных¶

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

¶История

Концепция иерархических баз данных возникла в конце 1950-х — начале 1960-х годов как одна из первых попыток структурированного хранения данных на магнитных лентах и дисках. Первой коммерчески успешной иерархической СУБД стала система IMS (Information Management System), разработанная компанией IBM в 1966 году для программы «Аполлон» (NASA). IMS позволяла управлять огромными объёмами данных о поставках и деталях космического аппарата, где каждый компонент имел чёткую иерархию: ракета состояла из ступеней, ступени — из двигателей, двигатели — из узлов и так далее.

В 1960-х — 1970-х годах иерархические базы данных доминировали в мейнфреймовых системах, особенно в банковской сфере, авиастроении и государственных реестрах. Однако с развитием реляционной модели (Э. Кодд, 1970) и появлением SQL их популярность начала снижаться. Тем не менее, иерархические СУБД продолжали использоваться в нишевых областях, где производительность и предсказуемость структуры были критичны (например, в системах реального времени). В 1980-х — 1990-х годах с распространением персональных компьютеров иерархическая модель легла в основу таких систем, как Windows Registry (реестр Windows) и B-tree-индексы в файловых системах.

¶Основные понятия и структура

¶Узлы и связи

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

¶Типы связей

Основной тип связи — «один ко многим» (1:M). Например, один отдел может содержать много сотрудников, но каждый сотрудник принадлежит только одному отделу. В иерархической модели также возможна связь «многие ко многим» (M:M), но она реализуется через дублирование данных или использование виртуальных связей (например, через указатели), что усложняет модель.

¶Ограничения

• Строгая иерархия: каждый дочерний узел имеет только одного родителя. Это исключает возможность циклических ссылок и сетевых структур.
• Порядок следования: дочерние узлы обычно упорядочены (например, по ключу или времени добавления), что влияет на эффективность поиска.
• Доступ только через корень: для получения данных о дочернем элементе необходимо пройти по пути от корневого узла (например, /Отдел/Сотрудник/Имя).

¶Классификация иерархических баз данных

¶По способу хранения

1. Физические иерархические базы — данные хранятся непосредственно в виде дерева на носителе (например, IMS использует сегменты и указатели).
2. Логические иерархические базы — данные могут быть организованы в виде дерева на уровне приложения, но физически хранятся в реляционной или другой структуре (например, XML-базы данных, LDAP-каталоги).

¶По области применения

• Системы управления документами (например, IBM Content Manager).
• Реестры и каталоги (Active Directory, Windows Registry).
• Геоинформационные системы (иерархия административных границ).
• Биологические и медицинские классификаторы (таксономия видов, анатомические структуры).

¶Примеры иерархических баз данных

¶IMS (IBM)

IMS — классическая иерархическая СУБД, работающая на мейнфреймах IBM. Данные организованы в сегменты (аналог записей), связанные через указатели. IMS поддерживает два типа организации: HSAM (Hierarchical Sequential Access Method) — последовательный доступ, и HDAM (Hierarchical Direct Access Method) — прямой доступ через хеш-таблицы. До сих пор используется в крупных банках и страховых компаниях для обработки транзакций (например, в системах бронирования авиабилетов).

¶LDAP (Lightweight Directory Access Protocol)

LDAP — протокол доступа к иерархическим каталогам, часто реализуемый в виде базы данных (например, OpenLDAP, Microsoft Active Directory). Данные организованы в виде дерева записей (entries), где каждая запись имеет атрибуты и уникальное имя (DN — distinguished name). LDAP широко применяется для хранения учётных записей пользователей, групп и политик безопасности в корпоративных сетях.

¶XML-базы данных

Хотя XML не является СУБД в классическом смысле, иерархическая структура XML-документов (вложенные элементы) позволяет использовать их как базы данных. Примеры: BaseX, eXist-db. Такие системы поддерживают запросы XPath и XQuery, позволяя извлекать данные по пути (например, /root/child/grandchild).

¶Windows Registry

Реестр Windows — иерархическая база данных, хранящая настройки операционной системы и приложений. Структура состоит из ключей (аналог узлов) и значений (аналог полей). Ключи организованы в пять корневых разделов (например, HKEY_LOCAL_MACHINE, HKEY_CURRENT_USER), каждый из которых содержит подразделы.

¶Преимущества и недостатки

¶Преимущества

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

¶Недостатки

• Негибкость — добавление нового типа связи или изменение иерархии (например, перемещение узла) требует перестройки всей структуры и, часто, перезагрузки базы данных.
• Избыточность данных — для реализации связи «многие ко многим» приходится дублировать данные (например, один и тот же сотрудник может числиться в нескольких отделах, что приведёт к копированию его записи).
• Сложность запросов — для получения данных, не соответствующих иерархии (например, «все сотрудники, родившиеся в 1990 году»), требуется обход всего дерева, что неэффективно.
• Отсутствие стандартного языка запросов — в отличие от SQL, для иерархических баз нет единого универсального языка; каждая СУБД использует собственный API (например, DL/I для IMS).

¶Применение в современном мире

Несмотря на доминирование реляционных и NoSQL-баз данных, иерархические модели продолжают использоваться в следующих областях:

• Системы управления конфигурацией (например, хранение параметров устройств в сетевом оборудовании).
• Библиотечные и архивные каталоги (классификация по разделам и подразделам).
• Графические движки (иерархия сцен в 3D-моделировании, где объект может содержать дочерние объекты).
• Встраиваемые системы (например, хранение данных о компонентах в автомобильной электронике).

В 2020-х годах интерес к иерархическим базам данных возродился в контексте графовых баз данных (например, Neo4j, OrientDB), которые позволяют моделировать сложные иерархии с множественными родителями и циклами, но при этом сохраняют производительность для древовидных запросов.

¶Источники

• Date, C. J. «An Introduction to Database Systems» (8th edition). Addison-Wesley, 2004.
• Elmasri, R., Navathe, S. B. «Fundamentals of Database Systems» (7th edition). Pearson, 2016.
• IBM Corporation. «IMS Version 15: Introduction». IBM Redbooks, 2020.
• Microsoft Corporation. «Windows Registry Information for Advanced Users». Microsoft Docs, 2023.
• W3C. «XML Path Language (XPath) 3.1». W3C Recommendation, 2017.