О хранении деревьев

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

CREATE TABLE Data
    (
      ID INT NOT NULL
             IDENTITY
             PRIMARY KEY
    , Data NVARCHAR(55) NOT NULL
    )

К сожалению почти все известные мне программисты идут по самому простому и очевидному пути — добавляют в таблицу столбец с ссылкой на родителя:

ALTER TABLE dbo.Data ADD ParentID INT REFERENCES dbo.Data(ID)

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

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

Как мне кажется, оптимальным решением для хранения деревьев в БД является разделение данных как таковых и их иерархии в разные сущности. Для хранения иерархии вводится вспомогательная таблица. Эта таблица хранит все существующие пути по дереву, а не только те, которые описывают связь родитель-потомок.

CREATE TABLE DataTree
    (
      ParentID INT NOT NULL
                   REFERENCES dbo.Data ( ID )
    , ChildID INT NOT NULL
                  REFERENCES dbo.Data ( ID )
    , Level INT NOT NULL
    , PRIMARY KEY ( ParentID , ChildID )
    )

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

  • Добавить элемент в иерархическую структуру в качестве корня;
  • Удалить элемент, являющийся листом (листом называют элементы, не имеющие потомков), из иерархической структуры;
  • Задать элементу нового родителя.
    Все остальные команды, изменяющие иерархию, могут быть выражены через эти три. Рассмотрим для начала три базовые команды.

Добавление нового элемента

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

CREATE PROCEDURE DataTree_AddElementAsRoot @ElementID INT
AS
BEGIN
    SET NOCOUNT ON

    INSERT  dbo.DataTree
            ( ParentID , ChildID , Level )
    VALUES
            ( @ElementID , @ElementID , 1 )
END

Удаление листа

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

CREATE PROCEDURE dbo.DataTree_DeleteLeaf @ElementID INT
AS
BEGIN
    SET NOCOUNT ON

    IF NOT EXISTS ( SELECT
                              *
                      FROM
                              dbo.DataTree AS dt
                      WHERE
                              ( 1 = 1 )
                              AND ( dt.ParentID = @ElementID )
                              AND ( dt.Level > 1 ) )
    DELETE FROM
            dbo.DataTree
    WHERE
            ( 1 = 0 )
            OR ( ParentID = @ElementID )
            OR ( ChildID = @ElementID )
END

Задание нового родителя

Это, пожалуй, единственная процедура в которой надо хоть немного подумать. Состоит перенос элемента с его поддеревом из двух частей. Сначала необходимо отсоединить всё поддерево от его родителей (хотя корректнее сказать не только от родителей, но и от всех предков). Затем необходимо вставить строки, соответствующие новым родителям поддеререва. Особо хочу обратить ваше внимание на то, что тут мы используем самый настоящий CROSS JOIN, чтобы получить декартово произведение.

CREATE PROCEDURE DataTree_MoveElement
    @MoveID INT
  , @ParentID INT
AS
BEGIN
    SET NOCOUNT ON

    DELETE FROM
            dbo.DataTree
    WHERE
            ( 1 = 1 )
            AND ( ChildID IN ( SELECT
                                        tc.ChildID
                                FROM
                                        dbo.DataTree AS tc
                                WHERE
                                        ( 1 = 1 )
                                        AND ( tc.ParentID = @MoveID ) ) )
            AND ( ParentID IN ( SELECT
                                         tp.ParentID
                                 FROM
                                         dbo.DataTree AS tp
                                 WHERE
                                         ( 1 = 1 )
                                         AND ( tp.ChildID = @MoveID )
                                         AND ( tp.ParentID <> tp.ChildID ) ) )

    INSERT  INTO dbo.DataTree
             (
                     ParentID
                   , ChildID
                   , Level
             )
             SELECT
                     supertree.ParentID
                   , subtree.ChildID
                   , supertree.Level + subtree.Level
             FROM
                     dbo.DataTree AS supertree
                     CROSS JOIN dbo.DataTree AS subtree
             WHERE
                     ( 1 = 1 )
                     AND ( supertree.ChildID = @ParentID )
                     AND ( subtree.ParentID = @MoveID )
END

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

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

Иерархия должностей

Иерархия должностей

С помощью описанных выше процедур мы создали записи в БД. Теперь, предположим, мы хотим узнать всех сотрудников, подчиняющихся директору IT. Для этого выполним простой запрос:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ParentID = 1 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
1 IT-директор 2 Руководитель управления разработки и сопровождения ПО 2
1 IT-директор 3 Руководитель отдела методологии и анализа ПО 2
1 IT-директор 4 Руководитель управления технической поддержки 2
1 IT-директор 5 Старший программист 3
1 IT-директор 8 Руководитель группы тестирования 3
1 IT-директор 10 Аналитик 3
1 IT-директор 11 Руководитель отдела системного администрирования 3
1 IT-директор 12 Системный администратор 4
1 IT-директор 9 Тестировщик 4
1 IT-директор 6 Ведущий программист 4
1 IT-директор 7 Инженер-программист 5

В результате мы видим не только непосредственных подчинённых IT-директора, но и всю цепочку иерархий с уровнями. Если нам надо получить только непосредственных подчинённых — просто добавим ограничение на уровень:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ParentID = 1 )
    AND ( dt.Level = 2 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
1 IT-директор 2 Руководитель управления разработки и сопровождения ПО 2
1 IT-директор 3 Руководитель отдела методологии и анализа ПО 2
1 IT-директор 4 Руководитель управления технической поддержки 2

Самое интересное в этой структуре то, что все уровни относительны. Т.е.относительно IT-директора тестировщик находится на четвёртом уровне вложенности, а вот относительно руководителя группы тестирования на втором:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ParentID = 8 )
    AND ( dt.Level = 2 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
8 Руководитель группы тестирования 9 Тестировщик 2

Определить цепочку руководителей тоже не составит труда:

SELECT
    dt.ParentID
  , dtp.Data
  , dt.ChildID
  , dtc.Data
  , dt.Level
FROM
    dbo.DataTree AS dt
    INNER JOIN dbo.Data AS dtp
        ON ( 1 = 1 )
           AND ( dtp.ID = dt.ParentID )
    INNER JOIN dbo.Data AS dtc
        ON ( 1 = 1 )
           AND ( dtc.ID = dt.ChildID )
WHERE
    ( 1 = 1 )
    AND ( dt.ParentID <> dt.ChildID )
    AND ( dt.ChildID = 7 )
ORDER BY
    dt.Level
ParentID Data ChildID Data Level
6 Ведущий программист 7 Инженер-программист 2
5 Старший программист 7 Инженер-программист 3
2 Руководитель управления разработки и сопровождения ПО 7 Инженер-программист 4
1 IT-директор 7 Инженер-программист 5

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

P.S. Также особенностью этого способа хранения деревьев является встроенная поддержка корректности. За счёт ограничения первичного ключа не удастся замкнуть дерево в цикл.

О хранении деревьев: 1 комментарий

  1. yandex.ru Миша 1

    Идея радикальная, конечно. На мой взгляд простота селекта для выборки иерархии очень субъективна. По мне так это муторнее чем классический подход оракула. В оракле работа с иерархией очень удобна через connect by.

    В Postgres есть with recursive. ЕМНИП его хотели стандартизировать, поэтому и в оракулах недавно появился. Стало быть в MSSQL должен быть. (Извиняюсь, гуглить версии лень :))

    Тем не менее, подход возьму на заметку, поскольку есть система в которой вынужден писать на HQL, который иерархические запросы не поддерживает. Здесь это актуально.

Добавить комментарий