DOC.PROTOTYPES.RU

Главная > Базы данных > Деревья SQL > Nested Sets > Теория >

Использование деревьев Nested Sets

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

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

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

Дерево Nested Set

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

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

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

SQL код (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)
);

Где:

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

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

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

SQL код (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):

SQL код (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
Nested Sets: Подчиненные узлы

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

SQL код (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
Nested Sets: родительская ветка

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

SQL код (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
Nested Sets: Подчиненные узлы и родительская ветка

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

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

SQL код (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 - в котором хранится идентификатор родительского узла.

Сергей Томулевич aka Phoinix (01.06.2005, ред. 12.01.2010 г.)

Еще статьи по теме:

Valid HTML 4.01 Transitional
Copyright © 2011 Сергей Томулевич