Nested Sets. Управление

Обновлено: 14 февраля, 2025

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

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

Пусть [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];

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

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

Ссылки по теме:

Опубликовано: 14 февраля, 2025

КОНСАЛТИНГ 
ПО POSTGRESQL

Консалтинг — 
это когда мы сами выполняем работу

ПОДРОБНЕЕ
Метки
ACL Adjacency List Contrib DevOps Extensions GRANT Linux ltree Materialized Path Nested Sets nginx ngx_http_dav_module ngx_http_image_filter_module ngx_http_map_module ngx_http_proxy_module ngx_http_random_index_module ngx_http_secure_link_module pg_hba.conf PostgreSQL privileges REVOKE Trees Ubuntu Web ZFS Деревья Индекс Миграция Оптимизация запросов триггеры

ЕЩЕ СТАТЬИ ПО ДАННОЙ ТЕМЕ

Преимущества и недостатки PostgreSQL в мире бизнес-данных

Пользователи сообщают о разнице в производительности при миграции. PostgreSQL сталкивается с проблемами при работе с некоторыми запросами, особенно по сравнению с SQL Server. Усовершенствования возможны через многопоточность и улучшенное кэширование.

Читать далее »

Поддержка Postgre SQL

Поддержка — это когда у вас возникает техническая
проблема с существующей системой,
и вам необходимо некоторое руководство

ПОДРОБНЕЕ