Создание узла
Создание узла – самое простое действие над деревом. Для того, что бы его осуществить нам потребуется уровень и правый ключ родительского узла (узел в который добавляется новый), либо максимальный правый ключ, если у нового узла не будет родительского.
Пусть [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 < [left_key];Сдвигаем последующие узлы (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):
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];Замечания те же, что и при перемещении ветки вверх по дереву.
На этом в общем-то все, в итоге получаем только четыре основных действия, основную сложность составляет подготовка переменных к перемещению узла.