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

Цель статьи не описать все возможные способы хранения таких данных,  а в сжатом виде виде описать два часто встречающихся  подхода и область их наилучшего применения.

1.  Узел хранит информацию о родителе. Это  классика.

CREATE TREE_NODE (ID INT ..., PARENT_ID INT, ...);

Все очень просто –  узел хранит идентификатор родительского узла. Самая простая схема.

Такую схему удобно использовать когда:

Добавление и удаление детей происходит чаще, чем поиск по деревьям.  Структура дерева постоянно меняется. Например идет процесс моделирования какой-то древовидной структуры и нам необходимо сохранять ее состояние в базе данных. В качестве примера можно привести программу в которой пользователь описывает иерархию свой организации.  Другой пример – сохранение в виде дерева информации о структуре разрабатываемого небольшого веб-сайта.

Другой вариант использования, когда в основном  требуются выборки на уровне одного поколения – получить список  “детей” у данного узла или получить информацию о родителе. Например, если мы используем асинхронное получение узлов в дереве.  Тогда дерево отображается не сразу, а после нажатия пользователем на соответствующий узел, после которого идет обращение к веб-серверу на получение данных. Например, как это выглядит в  Ext GWT (GXT).

Кстати, в некоторых базах данных существует уже готовые механизмы для работы с деревьями. В частности в ORACLE это CONNECT BY.

2. Вложенные множества.  Узел хранит в себе информацию о своем расположение в дереве.

CREATE TREE_NODE (ID INT ...,  LEFT INT...,  RIGHT INT...) ;

О вложенных множествах написано сейчас в интернете уже предостаточно. Основную идею можно понять из картинки.

и следующего SQL запроса (получение всей ветки для C.1):

SELECT id FROM tree WHERE left <= 5  AND right => 6 ORDER BY left; -- в итоге получим узлы A, B.2, C.1

Пример использования:

Возьмем вымышленную семью N, которая очень тщательно следит за своим семейным бюджетом.  Предположим у нее есть классификатор статей расходов бюджета, он может выглядеть приблизительно так:

1. Расходы семьи N
   1. Затраты на IT
      1. Техника
         1. Компьютер
            1. Персональный
            2. Нетбук
         2. Комплектующие
            1. Жесткие диски
            2. Модули памяти
            3. Блоки питания
         3. Манипуляторы и клавиатура
            1. Мыши
            2. Клавиатура
         4. Расходные материалы
            1. Картриджы
            2. Компакт-диски
               1. CD
               2. DVD
            3. Другое
         5. Другое
      2. Оплата интернета
      3. Программное обеспечение
   2. Продукты питания
      1. Мясо
      2. Алкоголь
         1. Пиво
         2. Водка
2. и т.д.

То есть содержать около 5 (пяти) уровней вложенности.  Для организации уровень вложенности может запросто превышать 10 ступеней.  Теперь, если семье N нужно будет разложить чек из  “Ашана” содержаший  около 20-60 покупок по соответствующим статьям бюджета,  то они смогут воспользоваться теорией вложенных множеств и единичными SQL запросами получат ответ на вопрос “в какие категории попадает их покупка?”.

Например:  Купили мышь. Получаем ветку “мышь” -> “манипуляторы и клавиатура” -> “техника”->”затраты на IT”.  Вся ветка благодаря вложенным множествам получается за один запрос.  Далее записываем данные о расходах, а затем  проверяем нет ли превышения бюджета по каждой статье расхода.

Внимание! При внесении изменений в саму структуру дерева приходиться изменять значения left и right у большого количества строк. Поэтому когда структура меняется очень часто пользоваться вложенными множествами становиться не так удобно.

Итог. Как лучше хранить иерархические данные?

Используем классику если дерево часто меняется или нам нужны поверхностные выборки.

Используем вложенные множества  в тех случаях, когда структура дерева меняется редко и нам нужна быстрая навигация по нему.

Для получение детальной информации относительно реализации следует обратиться к поисковым системам (google, yandex).  Ключевые слова – вложенные множества, nested set, иерархическая структура базы данных.

Из авторитетных источником можно порекомендовать например документацию по mysql.

Любое использование либо копирование материалов или подборки материалов сайта, элементов дизайна и оформления допускается лишь с разрешения правообладателя и только со ссылкой на источник: programador.ru

Телеграм канал: @prgrmdr
Почта для связи: vit [at] programmisty.com