DOC.PROTOTYPES.RU

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

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

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

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

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

UPDATE my_tree
    SET
        left_key = left_key + 2,
        right_key = right_key + 2
    WHERE
        left_key > [right_key];

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

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

UPDATE my_tree
    SET right_key = right_key + 2
    WHERE
        right_key >= [right_key] AND
        left_key < [right_key];

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

INSERT INTO my_tree
    SET
        left_key = [right_key],
        right_key = [right_key] + 1,
        level = [level] + 1
        ...;

Теперь можно объединить первые два запроса в один (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):

DELETE FROM my_tree
    WHERE
        left_key >= [left_key] AND
        right_key <= [right_key];

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

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

Обновление родительской ветки (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):

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).

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. Ключи и уровень перемещаемого узла;

SELECT level, left_key, right_key 
    FROM my_tree 
    WHERE id = [id];

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

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

SELECT level 
    FROM my_tree 
    WHERE id = [id_up];

Получаем [level_up]

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

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

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

• При простом перемещении в другой узел;

SELECT (right_key – 1) AS right_key
    FROM my_tree
    WHERE id = [id нового родительского узла];

• При изменении порядка, когда родительский узел не меняется – правый ключ узла за которым будет стоять перемещаемый;

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

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

• При переносе узла в корень дерева – максимальный правый ключ ветки;

SELECT MAX(right_key)
    FROM my_tree;

• При поднятии узла на уровень выше – правый ключ старого родительского узла

SELECT right_key 
    FROM my_tree 
    WHERE level = [level];

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

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

• [skew_level] = [level_up] - [level] + 1 - смещение уровня изменяемого узла;
• [skew_tree] = [right_key] - [left_key] + 1 - смещение ключей дерева;

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

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).

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

• Для левого ключа:
• • левый ключ узла меньше [left_key]
  • левый ключ узла больше [right_key_near]

• Для правого ключа:
• • правый ключ узла меньше [left_key]
  • правый ключ узла больше [right_key_near]

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

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

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

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];

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

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]);

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

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]
  • левый ключ узла меньше [right_key_near]

• Для правого ключа:
• • правый ключ узла больше [right_key]
  • правый ключ узла меньше или равно [right_key_near]

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

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

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];

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

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]);

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

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];

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

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