Nested Sets. Введение

Что это такое?

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

Одним из методов хранения древовидных структур является Nested Sets (Вложенные множества).

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

На схеме представлено дерево, описанное по всем правилам метода «Вложенных множеств». Квадратами обозначены узлы дерева, синие цифры в верхнем правом и верхнем левом углах узла — уровень и уникальный идентификатор соответственно, а красные цифры в нижних углах — это левый и правый ключ. Именно в этих двух цифрах — левом и правом ключе заложена вся информация о дереве. И если информацию о ключах занести в базу данных, то работа с деревом намного упрощается. Обратите внимание на то, в каком порядке проставлены эти ключи. Если мысленно пройтись по порядку от 1 до 32, то вы обойдете все узлы дерева слева направо. Фактически это путь обхода всех узлов дерева слева направо.

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

Создадим таблицу, где мы будем хранить наше дерево (1):

CREATE
  my_tree (
    id         INTEGER       NOT NULL,
    left_key   INTEGER       NOT NULL,
    right_key  INTEGER       NOT NULL,
    level      INTEGER       NOT NULL DEFAULT 0,
    name       TEXT,
    ...
PRIMARY KEY
    id, 
INDEX
    left_key (left_key, right_key, level)
);

Где:

• left_key — Левый ключ узла. Указывает на точку отсчета начала ветки. Так же является полем сортировки дерева;
• right_key — Правый ключ узла. Указывает на точку останова конца ветки. Так же используется для посчета дочерних узлов ветки;
• level — Уровень узла. Так же показывает количество родителей узла;

Как использовать?

Теперь определим, какие данные мы можем из неё (таблицы) выбрать:

1. Собственно само дерево (2):

SELECT
    id,
    name,
    level 
FROM
    my_tree
ORDER BY
    left_key;

В итоге, после небольшой обработки (в которой level играет роль множителя отступа), получим следующий список:

• Узел 1
  • Узел 2
    • Узел 5
      • Узел 10
      • Узел 11
  • Узел 3
    • Узел 6
    • Узел 7
      • Узел 12
      • Узел 13
      • Узел 14
    • Узел 8
  • Узел 4
    • Узел 9
      • Узел 15
      • Узел 16

2. Выбор подчиненных узлов (за отправной узел возьмем «Узел 7» его ключи [left_key], [right_key] и уровень [level]) (3):

SELECT
    id,
    name,
    level 
FROM
    my_tree
WHERE
    left_key >= [left_key]
  AND
    right_key <= [right_key]
ORDER BY
    left_key;

В итоге получаем:

3. Выбор родительской «ветки» (4):

SELECT
    id,
    name,
    level
FROM
    my_tree
WHERE
    left_key <= [left_key]
  AND
    right_key >= [right_key]
ORDER BY
    left_key;

В итоге получаем:

4. Выбор ветки в которой участвует наш узел (5):

SELECT
    id,
    name,
    level
FROM
    my_tree
WHERE
    right_key > [left_key]
  AND
    left_key < [right_key]
ORDER BY
    left_key;

В итоге получаем:

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

Единственным затруднением может возникнуть выборка родительского узла, чтобы его получить можно сделать запрос (6):

SELECT
    id,
    name,
    level
FROM
    my_tree
WHERE
    left_key <= [left_key]
  AND
    right_key >= [right_key]
  AND
    level = [level] - 1
ORDER BY
    left_key;

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

Ссылки по теме

• https://postgres.men/database/trees/nested-sets-rules/
• https://postgres.men/database/trees/nested-sets-manage/
• https://postgres.men/database/postgresql/nested-sets-postgresql-triggers/