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

Определения и обозначения

Иерархическая модель данных — модель, в которой записи организованы в виде дерева и связаны отношениями «родитель — потомок». Дерево показывает, какие объекты подчинены другим, и задаёт порядок перехода между уровнями. Такая модель помогает представлять данные с понятной структурой: например, подразделения организации и работающих в них сотрудников. По положению записи в дереве можно определить, к какой части общей системы она относится.

Запись — совокупность данных об одном объекте; в иерархической модели записи располагаются в узлах дерева. Например, запись об ученике может содержать его имя и другие сведения, а запись о классе — номер и букву класса. Узел — это место записи в структуре, а не отдельный вид данных. Разделение объектов на записи нужно, чтобы связывать сведения о них по их месту в иерархии.

Корневая запись — запись верхнего уровня, у которой нет родительской записи. Она служит началом дерева, от которого идут ветви к записям следующих уровней. Например, в структуре «школа — классы — ученики» корнем будет запись о школе. Корень нужен как единая точка, от которой можно описать путь к любому объекту в этой структуре.

Родительская и дочерняя записи — связанные записи соседних уровней: у дочерней есть один родитель, а у родительской может быть несколько дочерних. В примере со школой класс является дочерней записью школы, а для учеников — родительской. Такие названия описывают не сами объекты, а их отношения друг к другу. Они помогают понять, в каком направлении устроено подчинение.

Как это устроено

Сначала объекты предметной области представляют записями, а затем распределяют по уровням: от общей категории к её частям. Это делают потому, что сведения часто имеют естественную последовательность подчинения. Например, в школе есть классы, а в классах учатся ученики; отдельный ученик относится к конкретному классу. Если расположить такие записи по уровням, становится понятно, где искать сведения и какие объекты связаны между собой.

Структура называется деревом, потому что ветви расходятся от одной корневой записи к узлам нижних уровней. Каждая запись, кроме корневой, подчинена одной записи предыдущего уровня, поэтому для неё существует единственный путь от корня. Это условие не позволяет ветви разветвляться так, чтобы один узел одновременно принадлежал разным родителям. Благодаря этому положение каждой записи можно определить однозначно.

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

Чтобы найти запись, проходят путь от корневой записи через промежуточные уровни. На каждом шаге выбирают нужную дочернюю запись, ориентируясь на известные сведения: сначала школу, затем класс, затем ученика. Такой поиск похож на движение по ветви дерева, а не на просмотр всех записей без порядка. Модель становится неудобной, если один объект должен одновременно относиться к нескольким родителям или если между объектами есть связи, не укладывающиеся в такую последовательность.

Устройство иерархической модели данных

Читайте таблицу сверху вниз: первые три строки показывают роли записей и их отношения, а последняя — способ перехода между уровнями. Один и тот же узел может быть родительским по отношению к записям ниже и дочерним по отношению к записи выше. Пример пути помогает проверить, что нужная запись действительно достижима от корня.

Разбор задач

Задача 1. Постройте иерархическую модель для данных о библиотеке: библиотека, отделы, книги в каждом отделе. Нужно определить, какая запись будет началом дерева, и установить, какие записи подчиняются друг другу. Отдельно проверим, можно ли для каждой книги указать один отдел.

1. Запись «Библиотека» ставим в корень: она обозначает всю систему, и у неё нет родительской записи.
2. Записи об отделах размещаем уровнем ниже, потому что каждый отдел входит в библиотеку. Библиотека становится для них родительской записью.
3. Записи о книгах помещаем ниже записей отделов. Каждая книга связана с тем отделом, в котором она находится, а отдел может иметь несколько книг.

Ответ. Структура имеет вид «библиотека → отдел → книга». Если одна и та же книга должна числиться сразу в нескольких отделах, условие единственного родителя не выполняется для одной записи книги; тогда понадобится иначе описать данные или выбрать другую модель.

Задача 2. В дереве «организация → отдел → сотрудник» найдите путь к сотруднику Иванову из отдела продаж. Здесь уже задано направление связей, поэтому не нужно перестраивать всё дерево. Важно последовательно выбрать нужную запись на каждом уровне, не пропуская промежуточный отдел.

1. Начинаем с корневой записи «Организация», так как путь к любой записи в дереве начинается от корня.
2. На следующем уровне выбираем запись «Отдел продаж», а не любой другой отдел. Она нужна как промежуточная запись между организацией и сотрудником.
3. В списке дочерних записей отдела выбираем запись «Иванов». Полученная цепочка связывает искомого сотрудника с корнем.

Ответ. Путь: «Организация → отдел продаж → Иванов». Если в организации несколько сотрудников с такой фамилией, одних названий в пути может быть недостаточно для однозначного выбора; тогда нужны дополнительные сведения о записи.

Задача 3. Проверьте, подходит ли иерархическая структура для модели «ученик → учебная группа», если один ученик может одновременно состоять в нескольких группах. Сначала определим, какое отношение должно быть у дочерней записи с родителями. Затем сравним его с условием задачи, а не только с удобством привычного рисунка.

1. В иерархическом дереве у каждой некорневой записи только один родитель.
2. Если ученик участвует в нескольких группах, для одной записи ученика пришлось бы указать несколько родителей — записи этих групп.
3. Такое отношение уже не соответствует дереву. Дублирование записи ученика в каждой группе может усложнить изменение и согласование его данных.

Ответ. Иерархическая структура не подходит для такого отношения без дополнительных решений: один ученик связан с несколькими группами. Следует рассмотреть модель, которая позволяет описывать связи многих объектов друг с другом.

Типичные ошибки

Ошибка — считать, что у дочерней записи может быть несколько родителей. Так думают, когда переносят в дерево отношения, привычные по реальной жизни, например участие ученика в нескольких группах. Но тогда у записи не будет единственного пути от корня. Проверьте себя: для каждой некорневой записи можно указать ровно одного родителя?

Ошибка — называть корневой любую запись верхнего уровня. Её допускают, если воспринимают корень просто как узел, расположенный выше остальных. Однако корневая запись в дереве одна и не имеет родителя. Проверка простая: если у записи есть родитель или таких записей несколько, она не является корнем.

Ошибка — путать уровень записи с её типом. Например, можно решить, что запись «класс» всегда должна стоять на одном и том же уровне в любой структуре. Но уровень определяется тем, как именно организовано конкретное дерево, а не названием объекта. Чтобы проверить себя, найдите путь от корня и посчитайте, сколько переходов отделяет от него запись.

Ошибка — полагать, что любую связь между данными удобно представить деревом. Это кажется верным, если смотреть только на отдельные пары объектов и не учитывать связи с другими узлами. Но модель ограничена отношением подчинения и затрудняет описание нескольких родителей. Перед построением проверьте, образуют ли данные уровни и можно ли для каждого узла, кроме корня, выбрать одного родителя.

Связь с другими темами

Для работы с иерархической моделью нужно понимать, что такое база данных, запись и структурирование информации. Запись представляет отдельный объект, а структурирование помогает расположить объекты так, чтобы связи между ними были понятны. Если эти понятия знакомы, дерево можно читать как упорядоченную систему записей, а не просто как схему с ветвями.

Иерархическую модель полезно сопоставлять с сетевой и реляционной моделями данных. Такое сравнение помогает выбрать способ представления базы по характеру связей: дерево подходит для подчинения, но не всегда — для отношений между многими объектами. Поэтому при выборе учитывают не только то, как данные выглядят, но и какие связи требуется хранить.

Что запомнить

• Иерархическая модель данных имеет структуру дерева.
• У дерева есть одна корневая запись.
• Каждая некорневая запись имеет ровно одного родителя.
• У родительской записи может быть несколько дочерних.
• Путь к записи проходит от корня через её предков.
• Модель подходит для данных с отношениями подчинения.