DOC.PROTOTYPES.RU

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

Управление деревьями Nested Sets

Создание узла:

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

Пусть [right_key] – правый ключ родительского узла, или максимальный правый ключ плюс единица (если родительского узла нет, то узел с максимальным правым ключом не будет обновляться, соответственно, чтобы не было повторов, берем число на единицу большее). [level] – уровень родительского узла, либо 0, если родительского нет.

Обновляем ключи существующего дерева, узлы стоящие за родительским узлом (1):

SQL код (1)
UPDATE my_tree
    SET
        left_key = left_key + 2,
        right_key = right_key + 2
    WHERE
        left_key > [right_key];

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

Обновляем родительскую ветку (2):

SQL код (2)
UPDATE my_tree
    SET right_key = right_key + 2
    WHERE
        right_key >= [right_key] AND
        left_key < [left_key];

Сдвигаем последующие узлы (3):

SQL код (3)
UPDATE my_tree
    SET
        left_key = left_key + 2,
        right_key = right_key + 2
    WHERE
        right_key >= [right_key] AND
        left_key >= [left_key];

Теперь добавляем новый узел (3):

SQL код (3)
INSERT INTO my_tree
    SET
        left_key = [right_key],
        right_key = [right_key] + 1,
        level = [level] + 1
        ...;

Теперь можно объединить первые два запроса в один (4), что бы не делать лишних действий.

SQL код (4)
UPDATE my_tree
    SET
        right_key = right_key + 2,
        left_key = CASE WHEN left_key > [right_key]
                        THEN left_key + 2
                        ELSE left_key
                   END
    WHERE
        right_key >= [right_key];

Удаление узла

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

Пусть [left_key] – левый ключ удаляемого узла, а [right_key] – правый

Удаляем узел (ветку) (5):

SQL код (5)
DELETE FROM my_tree
    WHERE
        left_key >= [left_key] AND
        right_key <= [right_key];

Обновляем ключи оставшихся веток:

Как и в случае с добавлением обновление происходит двумя командами: обновление ключей родительской ветки и обновление ключей узлов, стоящих за родительской веткой. Следует правда учесть, что обновление будет производиться в другом порядке, так как ключи у нас уменьшаются.

Обновление родительской ветки (6):

SQL код (6)
UPDATE my_tree
    SET
        right_key = right_key – ( [right_key] - [left_key] + 1 ) --- *
    WHERE
        right_key > [right_key] AND
        left_key < [left_key];

* Так как мы не знаем точное количество подчиненных узлов, мы вычисляем длину диапазона (смещения) ключей удаляемой ветки (узла).

Обновление последующих узлов (7):

SQL код (7)
UPDATE my_tree
    SET
        left_key = left_key – ( [right_key] - [left_key] + 1 ),
        right_key = right_key – ( [right_key] - [left_key] + 1 )
    WHERE
        left_key > [right_key];

Теперь можно объединить последние два запроса в один, что бы не делать лишних действий (8).

SQL код (8)
UPDATE my_tree
    SET
        left_key = CASE WHEN left_key > [left_key]
                        THEN left_key – ( [right_key] - [left_key] + 1 )
                        ELSE left_key
                   END,
        right_key = right_key – ( [right_key] - [left_key] + 1 )
    WHERE
        right_key > [right_key];

Перемещение узла

Перемещение узла – самое сложное действие в управлении деревом. На схеме показаны области, на которые можно разделить наше дерево. Из её можно увидеть, что узел может перемещаться только в две разные области: вышестоящих и нижестоящих узлов. Вообще, чем примечательно использование Nested Sets, что с помощью двух ключей ветки возможен выбор узлов любой области.

Схема зон дерева

1. Вверх по дереву (в область вышестоящих узлов), включает в себя:

2. Вниз по дереву (в область нижестоящих узлов), включает в себя.

Для начала выберем ключи следующих узлов:

1. Ключи и уровень перемещаемого узла;

SQL код (9)
SELECT level, left_key, right_key 
    FROM my_tree 
    WHERE id = [id];

Получаем [level], [left_key], [right_key]

2. Уровень нового родительского узла (если узел перемещается в "корень" то сразу можно подставить значение 0):

SQL код (10)
SELECT level 
    FROM my_tree 
    WHERE id = [id_up];

Получаем [level_up]

3. Правый ключ узла за который мы вставляем узел (ветку):

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

Данная переменная берется в зависимости от действия:

SQL код (11)
SELECT (right_key – 1) AS right_key
    FROM my_tree
    WHERE id = [id нового родительского узла];
SQL код (12)
SELECT left_key, right_key 
    FROM my_tree 
    WHERE id = [id соседнего узла с который будет(!) выше (левее)]; --****

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

SQL код (13)
SELECT MAX(right_key)
    FROM my_tree;
SQL код (14)
SELECT right_key 
    FROM my_tree 
    WHERE level = [level];

Получаем [right_key_near] и [left_key_near] (для варианта изменения порядка)

4. Определяем смещения:

Выбираем все узлы перемещаемой ветки:

SQL код (15)
SELECT id 
    FROM my_tree 
    WHERE
        left_key >= [left_key] AND
        right_key <= [right_key];

Получаем [id_edit] - список id номеров перемещаемой ветки.

Так же требуется определить: в какую область перемещается узел, для этого сравниваем [right_key] и [right_key_near], если [right_key_near] больше, то узел перемещается в облась вышестоящих узлов, иначе - нижестоящих (почему существует разделение описано ниже).

Где у нас изменяются ключи по дереву во время переноса узла показано на схеме:

Схема изменений ключей при перемещении узлов

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

Хочу обратить внимание на то что у нас есть разница изменения ключей дерева в зависимости от того, в какую область перемещается узел (увеличение <-> уменьшение), а так же то, что правая родительская ветка может быть как старой, так и новой родительской веткой, то же самое и с левой родительской веткой. Поэтому порядок обновления ключей и условия выбора диапазонов областей различны, в зависимости от вида перемещения (вверх или вниз).

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

При перемещении вверх по дереву выделяем следующие области:

Зона изменений левых ключей при перемещении узла вверх
Зона изменений правых ключей при перемещении узла вверх

Хотел бы обратить внимание на то, что в условии с [right_key_near] и [left_key] дерево разделяется на разные области так как эти переменные сравниваются с разными ключами.

Определяем смещение ключей редактируемого узла [skew_edit] = [right_key_near] - [left_key] + 1.

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

SQL код (16)
UPDATE my_tree
    SET right_key = right_key + [skew_tree]
    WHERE
        right_key < [left_key] AND
        right_key > [right_key_near];
   
UPDATE my_tree
    SET left_key = left_key + [skew_tree]
    WHERE
        left_key < [left_key] AND
        left_key > [right_key_near];

Теперь можно переместить ветку:

SQL код (17)
UPDATE my_tree
    SET
        left_key = left_key + [skew_edit],
        right_key = right_key + [skew_edit],
        level = level + [skew_level]
    WHERE
        id IN ([id_edit]);

После оптимизации этих запросов получаем всего один:

SQL код (18)
UPDATE my_table
    SET
        right_key = CASE WHEN left_key >= [left_key]
                         THEN right_key + [skew_edit]
                         ELSE CASE WHEN right_key < [left_key]
                                   THEN right_key + [skew_tree]
                                   ELSE right_key
                              END
                    END,
        level = CASE WHEN left_key >= [left_key]
                     THEN level + [skew_level]
                     ELSE level
                END,
        left_key = CASE WHEN left_key >= [left_key]
                        THEN left_key + [skew_edit]
                        ELSE CASE WHEN left_key > [right_key_near]
                                  THEN left_key + [skew_tree]
                                  ELSE left_key
                             END
                   END
    WHERE
        right_key > [right_key_near] AND
        left_key < [right_key];

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

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

При перемещении вниз по дереву выделяем следующие области:

Зона изменений левых ключей при перемещении узла вниз
Зона изменений правых ключей при перемещении узла вниз

Опять же порядок не имеет значения, поэтому просто делаем команды на обновление. Правда хочу обратить внимание на тот факт, что в условии: "левый ключ узла меньше [right_key_near]" узел в котором находится [right_key_near] тоже попадает в диапазон изменения, следует иметь ввиду, что при сравнении не однотипных ключей (правый <-> левый) текущий узел попадает или не попадает в диапазон без использования равенства в условии.

Определяем смещение ключей редактируемого узла [skew_edit] = [right_key_near] - [left_key] + 1 - [skew_tree].

SQL код (19)
UPDATE my_tree
    SET
        right_key = right_key - [skew_tree]
    WHERE
        right_key > [right_key] AND
        right_key <= [right_key_near];
    
UPDATE my_tree
    SET
        left_key = left_key - [skew_tree]
    WHERE
        left_key < [left_key] AND
        left_key > [right_key_near];

Теперь можно переместить ветку:

SQL код (20)
UPDATE my_tree
    SET
        left_key = left_key + [skew_edit],
        right_key = right_key + [skew_edit],
        level = level + [skew_level]
    WHERE
        id IN ([id_edit]);

После оптимизации этих запросов получаем всего один:

SQL код (21)
UPDATE my_table
    SET
        left_key = CASE WHEN right_key <= [right_key]
                        THEN left_key + [skew_edit]
                        ELSE CASE WHEN left_key > [right_key]
                                  THEN left_key - [skew_tree]
                                  ELSE left_key
                             END
                    END,
        level = CASE WHEN right_key <= [right_key],
                     THEN level + [skew_level]
                     ELSE level
                END,
        right_key = CASE WHEN right_key <= [right_key]
                         THEN right_key + [skew_edit]
                         ELSE CASE WHEN right_key <= [right_key_near]
                                   THEN right_key - [skew_tree]
                                   ELSE right_key
                              END
                    END
    WHERE
        right_key > [left_key] AND
        left_key <= [right_key_near];

Замечания те же, что и при перемещении ветки вверх по дереву.

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

Сергей Томулевич aka Phoinix (01.06.2005, ред. 12.01.2010 г.)
Valid HTML 4.01 Transitional
Copyright © 2011 Сергей Томулевич