Что это такое?
О проблемах хранения деревьев в 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
- Узел 5
- Узел 3
- Узел 6
- Узел 7
- Узел 12
- Узел 13
- Узел 14
- Узел 8
- Узел 4
- Узел 9
- Узел 15
- Узел 16
- Узел 9
- Узел 2
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;
В итоге получаем:
- Узел 7
- Узел 12
- Узел 13
- Узел 14
3. Выбор родительской «ветки» (4):
SELECT
id,
name,
level
FROM
my_tree
WHERE
left_key <= [left_key]
AND
right_key >= [right_key]
ORDER BY
left_key;
В итоге получаем:
- Узел 1
- Узел 3
- Узел 7
- Узел 3
4. Выбор ветки в которой участвует наш узел (5):
SELECT
id,
name,
level
FROM
my_tree
WHERE
right_key > [left_key]
AND
left_key < [right_key]
ORDER BY
left_key;
В итоге получаем:
- Узел 1
- Узел 3
- Узел 7
- Узел 12
- Узел 13
- Узел 14
- Узел 7
- Узел 3
В общем, использование в условии запроса ключей узла можно выбрать любые данные связанные с этим узлом.
Единственным затруднением может возникнуть выборка родительского узла, чтобы его получить можно сделать запрос (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 — в котором хранится идентификатор родительского узла.