Nested Sets + PostgreSQL TRIGGER

Задача

Как удобно делать выборки из деревьев типа Nested Sets, и как не удобно им управлять. Как удобноуправлять деревьями типа id->parent_id, но как не удобно и накладно использовать рекурсии при выборках. Понятно, что прииспользовании модулей для управления деревьями часть проблемы снимается, но при этом процесс работы с базой данных несовсем прозрачен т.е. для изменения данных мы используем одни методы, для изменения расположения узла в дереве — другие,плюс еще транзакции не помешали бы. Эту нестыковку можно решить двумя способами:

• Использовать для работы с таблицей хранимые процедуры, в которой объединить оба метода обновления (вставки, удаления);
• Использовать триггеры, для исключения вообще каких-либо нестандартных методов работы;

Первый способ неудобен тем, что при изменении структуры таблицы, нам потребуется еще изменять процедуру, а так же бытьмаксимально внимательным, при работе с таблицей, что бы все изменения данных проходили через наши процедуры, а не прямымизапросами. Второй способ несколько утяжеляет тяблицу введением дополнительных булевых полей, а так же приходится делатьнекоторые «финты ушами», хотя позволяет добиться максимальной прозрачности работы.Первый способ — в топку, тем более где-то интернетах уже есть подобное решение.База данных — PostgreSQL, как актуальная мне на данный момент, дополнения для MySQL напишу позже.

Таблица

Итак, какие триггеры нам понадобятся:

• До вставки записи — для формирования разрыва в дереве и ключей для создаваемого узла;
• До обновления — для перестроения дерева и формирования ключей для обновляемого узла;
• После удаления — удаление разрыва в дереве оставшееся после удаления узла;

Грабли:

• На время работы триггеров, требуется лочить таблицу, или отдельное дерево, если у нес в одной таблице деревьев несколько;
• В PostgreSQL и MySQL в триггерах нельзя отключить рекурсию, вот так;

Пункт второй подробнее: В триггере до обновления, могут обновляться записи из той же таблицы, что повлечет за собой повторыйвызов триггера и так далее, так же и для триггера, вызываемого после удаления. Для того что бы понять вызван у нас запросиз триггера или нет, введем два дополнительных булевых поля, которые мы будем передавать в запросе как параметр (флаг) длятриггера, а не как данные. Почему именно два — расскажу позднее.Структуру таблицы сформируем сразу с учетом того, что у нас в ней будет храниться несколько деревьев.Объясню почему. Мне смешно до слез слушать глупых разработчиков, которые с пеной у рта доказывают, что мол, ай-ай-ай, прибольшом количестве узлов обновление узлов может затронуть все дерево, и это так тяжело для базы. Да, именно так. Не спорю.Только вот у меня еще ниразу не было огромного количества узлов в одном дереве потому, что:

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

Пример: Есть некоторый форум. В разделе форума 1'000 постов, у каждого поста 1'000 комментариев. Всего комментариев — 1'000'000.Так вот, раздел форума — НЕ является корневым узлом комментариев, так же как и посты НЕ являются узлами одного дерева, аявляются только разделителями деревьев. В итоге, у меня 1'000 раздельных деревьев по 1'000 комментариев. Обновление происходиттолько лишь в пределах максимум 1'000 записей. В некоторых случаях, если и этого много, разделителем деревьев являются комментариипервого уровня. В итоге, перестроение дерева не является такой уж нагрузкой на базу. Изучайте мат часть.Не будем о грустном, структура таблицы: SQL код (1)

CREATE
  ns_tree (
    id                      SERIAL,
    left_key                INTEGER       NOT NULL,
    right_key               INTEGER       NOT NULL,
    level                   INTEGER       NOT NULL DEFAULT 0,
    tree                    INTEGER       NOT NULL,    
    parent_id               INTEGER       NOT NULL DEFAULT 0,
    _trigger_lock_update    BOOLEAN       NOT NULL DEFAULT FALSE,
    _trigger_for_delete     BOOLEAN       NOT NULL DEFAULT FALSE,
    field_1                 ...,
    ...
PRIMARY KEY (id)
);
    

Собственно — _trigger_lock_update и _trigger_for_delete, являются нашими вспомогательными полями.Сразу сделаем функцию блокирующую дереве на изменение, пока транзакция не закончена: SQL код (2)

CREATE OR REPLACE FUNCTION lock_ns_tree(integer)
    RETURNS boolean AS
$BODY$
DECLARE tree_id ALIAS FOR $1;
    _id INTEGER;
BEGIN
    SELECT id
        INTO _id
        FROM ns_tree
        WHERE tree = tree_id FOR UPDATE;
    RETURN TRUE;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE
  COST 100;
ALTER FUNCTION lock_ns_tree(integer) OWNER TO user;
    

Создание записи

У нас есть 3 варианта добаления узла в дерево:

• Добавление в подчинение определенному узлу, тогда мы передаем parent_id;
• Добавление в определенную точку дерева, тогда мы передаем left_key;
• Добавление в конец дерева, тогда нам не требуется ничего дополнительно передавать;

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

CREATE OR REPLACE FUNCTION ns_tree_before_insert_func()
    RETURNS trigger AS
$BODY$
DECLARE
    _left_key       INTEGER;
    _level          INTEGER;
    _tmp_left_key   INTEGER;
    _tmp_right_key  INTEGER;
    _tmp_level      INTEGER;
    _tmp_id         INTEGER;
    _tmp_parent_id  INTEGER;
BEGIN
    PERFORM lock_ns_tree(NEW.tree);
-- Нельзя эти поля ручками ставить:
    NEW._trigger_for_delete := FALSE;
    NEW._trigger_lock_update := FALSE;
    _left_key := 0;
    _level := 0;
-- Если мы указали родителя:
    IF NEW.parent_id IS NOT NULL AND NEW.parent_id > 0 THEN
        SELECT right_key, "level" + 1
            INTO _left_key, _level
            FROM ns_tree
            WHERE id = NEW.parent_id AND
                  tree = NEW.tree;
    END IF;
-- Если мы указали левый ключ:
    IF NEW.left_key IS NOT NULL AND
       NEW.left_key > 0 AND 
       (_left_key IS NULL OR _left_key = 0) THEN
        SELECT id, left_key, right_key, "level", parent_id 
            INTO _tmp_id, _tmp_left_key, _tmp_right_key, _tmp_level, _tmp_parent_id
            FROM ns_tree
            WHERE tree = NEW.tree AND (left_key = NEW.left_key OR right_key = NEW.left_key);
        IF _tmp_left_key IS NOT NULL AND _tmp_left_key > 0 AND NEW.left_key = _tmp_left_key THEN
            NEW.parent_id := _tmp_parent_id;
            _left_key := NEW.left_key;
            _level := _tmp_level;
        ELSIF _tmp_left_key IS NOT NULL AND _tmp_left_key > 0 AND NEW.left_key = _tmp_right_key THEN
            NEW.parent_id := _tmp_id;
            _left_key := NEW.left_key;
            _level := _tmp_level + 1;
        END IF;
    END IF;
-- Если родитель или левый ключ не указан, или мы ничего не нашли:
    IF _left_key IS NULL OR _left_key = 0 THEN
        SELECT MAX(right_key) + 1
            INTO _left_key
            FROM ns_tree
            WHERE tree = NEW.tree;
        IF _left_key IS NULL OR _left_key = 0 THEN
            _left_key := 1;
        END IF;
        _level := 0;
        NEW.parent_id := 0; 
    END IF;
-- Устанавливаем полученные ключи для узла:
    NEW.left_key := _left_key;
    NEW.right_key := _left_key + 1;
    NEW."level" := _level;
-- Формируем развыв в дереве на месте вставки:
    UPDATE ns_tree
        SET left_key = left_key + 
            CASE WHEN left_key >= _left_key 
              THEN 2 
              ELSE 0 
            END,
            right_key = right_key + 2,
            _trigger_lock_update = TRUE
        WHERE tree = NEW.tree AND right_key >= _left_key;
    RETURN NEW;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE
  COST 100;
ALTER FUNCTION ns_tree_before_insert_func() OWNER TO user;

CREATE TRIGGER ns_tree_before_insert_tr
    BEFORE INSERT
    ON ns_tree
    FOR EACH ROW
    EXECUTE PROCEDURE ns_tree_before_insert_func();
    

Теперь некоторые пояснения:

• _trigger_lock_update и _trigger_for_delete — управляющие поля, поэтому их сразу сбрасываем не зависимо от пожеланий пользователя;
• Даже если мы указали parent_id — не факт, что такой узел у нас есть и то, что он в соответсвующем дереве. В текущем случае, если я не нахожу узла в данном дереве, то parent_id сбрасывается, и узел вставляется в конец дерева. Как вариант, можно фильтровать по дереву, а просто искать узел по id, тогда нужно будет обновлять поле tree создаваемого узла. Все зависит от приоритетности полей и конкретной реализации;
• Если мы указали левый ключ, то нам, как минимум, нужно вычислить родителя создаваемого узла, родителя определяем по принципу: если мы нашли узел по левому ключу, то родитель будет таким же как и у найденого узла, иначе если по правому, то родителем будет найденный нами узел, так же выстраиваем и уровень. Если же узел, не найден, то тогда вставляем в конец дерева, left_key при этом — сбрасывается;
• Во время формирования разрыва, дополнительно передается поле _trigger_lock_update — как раз таки для того, что бы триггер для UPDATE знал, что это обновление связано исключительно со структурой дерева, и никаких дополнительных вычислений и изменений структуры не требуется, так как передаются уже конечные значения ключей;

Изменение записи

Точнее данный триггер будет работать исключительно со структурой дерева, а не с изменяемыми данными.Основными параметрами принуждающие его к каким либо действиям являются parent_id или left_key(помня, конечно, о _trigger_lock_update как об управляющем параметре для триггера).Алгоритм простой: сначала координаты перемещения, потом перестраиваем дерево. SQL код (4)

CREATE OR REPLACE FUNCTION ns_tree_before_update_func()
  RETURNS trigger AS
$BODY$
DECLARE
    _left_key       INTEGER;
    _level          INTEGER;
    _skew_tree      INTEGER;
    _skew_level     INTEGER;
    _skew_edit      INTEGER;
    _tmp_left_key   INTEGER;
    _tmp_right_key  INTEGER;
    _tmp_level      INTEGER;
    _tmp_id         INTEGER;
    _tmp_parent_id  INTEGER;
BEGIN
    PERFORM lock_ns_tree(OLD.tree);
-- А стоит ли нам вообще что либо делать:
    IF NEW._trigger_lock_update = TRUE THEN
        NEW._trigger_lock_update := FALSE;
        IF NEW._trigger_for_delete = TRUE THEN
            NEW = OLD;
            NEW._trigger_for_delete = TRUE;
            RETURN NEW;
        END IF;
        RETURN NEW;
    END IF;
-- Сбрасываем значения полей, которые пользователь менять не может:
    NEW._trigger_for_delete := FALSE;
    NEW.tree := OLD.tree;
    NEW.right_key := OLD.right_key;
    NEW."level" := OLD."level";
    IF NEW.parent_id IS NULL THEN NEW.parent_id := 0; END IF;
-- Проверяем, а есть ли изменения связанные со структурой дерева
    IF NEW.parent_id = OLD.parent_id AND NEW.left_key = OLD.left_key
    THEN
        RETURN NEW;
    END IF;
-- Дерево таки перестраиваем, что ж, приступим:
    _left_key := 0;
    _level := 0;
    _skew_tree := OLD.right_key - OLD.left_key + 1;
-- Определяем куда мы его переносим:
-- Если сменен parent_id:
    IF NEW.parent_id <> OLD.parent_id THEN
-- Если в подчинение другому злу:
        IF NEW.parent_id > 0 THEN
            SELECT right_key, level + 1
                INTO _left_key, _level
                FROM ns_tree
                WHERE id = NEW.parent_id AND tree = NEW.tree;
-- Иначе в корень дерева переносим:
        ELSE
            SELECT MAX(right_key) + 1 
                INTO _left_key
                FROM ns_tree
                WHERE tree = NEW.tree;
            _level := 0;
        END IF;
-- Если вдруг родитель в диапазоне перемещаемого узла, проверка:
        IF _left_key IS NOT NULL AND 
           _left_key > 0 AND
           _left_key > OLD.left_key AND
           _left_key <= OLD.right_key 
        THEN
           NEW.parent_id := OLD.parent_id;
           NEW.left_key := OLD.left_key;
           RETURN NEW;
        END IF;
    END IF;
-- Если же указан left_key, а parent_id - нет
    IF _left_key IS NULL OR _left_key = 0 THEN
        SELECT id, left_key, right_key, "level", parent_id 
            INTO _tmp_id, _tmp_left_key, _tmp_right_key, _tmp_level, _tmp_parent_id
            FROM ns_tree
            WHERE tree = NEW.tree AND (right_key = NEW.left_key OR right_key = NEW.left_key - 1)
            LIMIT 1;
        IF _tmp_left_key IS NOT NULL AND _tmp_left_key > 0 AND NEW.left_key - 1 = _tmp_right_key THEN
            NEW.parent_id := _tmp_parent_id;
            _left_key := NEW.left_key;
            _level := _tmp_level;
        ELSIF _tmp_left_key IS NOT NULL AND _tmp_left_key > 0 AND NEW.left_key = _tmp_right_key THEN
            NEW.parent_id := _tmp_id;
            _left_key := NEW.left_key;
            _level := _tmp_level + 1;
        ELSIF NEW.left_key = 1 THEN
            NEW.parent_id := 0;
            _left_key := NEW.left_key;
            _level := 0;
        ELSE
           NEW.parent_id := OLD.parent_id;
           NEW.left_key := OLD.left_key;
           RETURN NEW;
        END IF;
    END IF;
-- Теперь мы знаем куда мы перемещаем дерево
        _skew_level := _level - OLD."level";
    IF _left_key > OLD.left_key THEN
-- Перемещение вверх по дереву
        _skew_edit := _left_key - OLD.left_key - _skew_tree;
        UPDATE ns_tree
            SET left_key =  CASE WHEN right_key <= OLD.right_key
                                 THEN left_key + _skew_edit
                                 ELSE CASE WHEN left_key > OLD.right_key
                                           THEN left_key - _skew_tree
                                           ELSE left_key
                                      END
                            END,
                "level" =   CASE WHEN right_key <= OLD.right_key 
                                 THEN "level" + _skew_level
                                 ELSE "level"
                            END,
                right_key = CASE WHEN right_key <= OLD.right_key 
                                 THEN right_key + _skew_edit
                                 ELSE CASE WHEN right_key < _left_key
                                           THEN right_key - _skew_tree
                                           ELSE right_key
                                      END
                            END,
                _trigger_lock_update = TRUE
            WHERE tree = OLD.tree AND
                  right_key > OLD.left_key AND
                  left_key < _left_key AND
                  id <> OLD.id;
        _left_key := _left_key - _skew_tree;
    ELSE
-- Перемещение вниз по дереву:
        _skew_edit := _left_key - OLD.left_key;
        UPDATE ns_tree
            SET
                right_key = CASE WHEN left_key >= OLD.left_key
                                 THEN right_key + _skew_edit
                                 ELSE CASE WHEN right_key < OLD.left_key
                                           THEN right_key + _skew_tree
                                           ELSE right_key
                                      END
                            END,
                "level" =   CASE WHEN left_key >= OLD.left_key
                                 THEN "level" + _skew_level
                                 ELSE "level"
                            END,
                left_key =  CASE WHEN left_key >= OLD.left_key
                                 THEN left_key + _skew_edit
                                 ELSE CASE WHEN left_key >= _left_key
                                           THEN left_key + _skew_tree
                                           ELSE left_key
                                      END
                            END,
                 _trigger_lock_update = TRUE
            WHERE tree = OLD.tree AND
                  right_key >= _left_key AND
                  left_key < OLD.right_key AND
                  id <> OLD.id;
    END IF;
-- Дерево перестроили, остался только наш текущий узел
    NEW.left_key := _left_key;
    NEW."level" := _level;
    NEW.right_key := _left_key + _skew_tree - 1;
    RETURN NEW;
END;
$BODY$
    LANGUAGE 'plpgsql' VOLATILE
    COST 100;
ALTER FUNCTION ns_tree_before_update_func() OWNER TO user;

CREATE TRIGGER ns_tree_before_update_tr
    BEFORE UPDATE
    ON ns_tree
    FOR EACH ROW
    EXECUTE PROCEDURE ns_tree_before_update_func();
    

Пояснения:

• Изначально, кроме параметра _trigger_lock_update мы проверяем так же параметр _trigger_for_delete. Это сделано потому, что во время удаления, мы не передавать параметры, как изменение поля, поэтому удаление записей триггером будем производить через UPDATE определенных записей. Впрочем более понятно станет далее;
• Опять же в данном случае, parent_id у нас боле приоритетный чем left_key, поэтому его проверяем первым;
• При проверке left_key мы выбираем изначально либо узел, который будет перед перемещаемым узлом (right_key = _left_key + 1), либо узел в который мы перемещаем узел (right_key = _left_key). При этом, у некоторых случаях результатом запроса будет возвращаться 2 узла, как будущий сосед, так и будущий родитель, что на логику никак не влияет, по этому LIMIT 1 установлен, что бы не просто не выбирать лишние данные, сортировка не важна, так как даже если результатом выборки будет 2 узла, они оба будут корректны, поэтому нам совершенно безразлично какой из них нам вернется. Но хочу обратить внимание, на то, что если мы указываем у перемещаемого узла left_key = 1, то естественно, что ни впередистоящего, ни родительского узла у нас не будет, для чего используем дополнительное условие "ELSIF NEW.left_key = 1";
• При перестроении дерева, дополнительным условием является "id <> OLD.id", это сделано потому, что мы не можем в триггере изменять запись, которую и так сейчас меняем.

Удаление записи

Вот с удалением сложнее всего. Во-первых, потому, что существует 2 принципа удаления узлов:

• Удаление узла с потомками;
• Удаление узла без потомков, при этом дочерние узлы смещаются по дереву на уровень вверх;

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

• Обновляем дочерние узлы на предмет установки поля (параметра) _trigger_for_delete;
• Удаляем дочерние узлы;
• Удаляем разрыв в ключах в дереве (перестаиваем дерево);

SQL код (5)

CREATE OR REPLACE FUNCTION ns_tree_after_delete_func()
    RETURNS trigger AS
$BODY$
DECLARE
    _skew_tree INTEGER;
BEGIN
    PERFORM lock_ns_tree(OLD.tree);
-- Проверяем, стоит ли выполнять триггер:
    IF OLD._trigger_for_delete = TRUE THEN RETURN OLD; END IF;
-- Помечаем на удаление дочерние узлы:
    UPDATE ns_tree
        SET _trigger_for_delete = TRUE,
            _trigger_lock_update = TRUE
        WHERE
            tree = OLD.tree AND
            left_key > OLD.left_key AND
            right_key < OLD.right_key;
-- Удаляем помеченные узлы:
    DELETE FROM ns_tree
        WHERE
            tree = OLD.tree AND
            left_key > OLD.left_key AND
            right_key < OLD.right_key;
-- Убираем разрыв в ключах:
    _skew_tree := OLD.right_key - OLD.left_key + 1;
    UPDATE ns_tree
        SET left_key = CASE WHEN left_key > OLD.left_key
                            THEN left_key - _skew_tree
                            ELSE left_key
                       END,
            right_key = right_key - _skew_tree,
            _trigger_lock_update = TRUE
        WHERE right_key > OLD.right_key AND
            tree = OLD.tree;
    RETURN OLD;
END;
$BODY$
    LANGUAGE 'plpgsql' VOLATILE
    COST 100;
ALTER FUNCTION ns_tree_after_delete_func() OWNER TO user;

CREATE TRIGGER ns_tree_after_delete_tr
    AFTER DELETE
    ON ns_tree
    FOR EACH ROW
    EXECUTE PROCEDURE ns_tree_after_delete_func();
    

Во втором решении просто смещаем дочернее дерево на уровень вверх, и удаляем разрыв ключей. SQL код (6)

CREATE OR REPLACE FUNCTION ns_tree_after_delete_2_func()
    RETURNS trigger AS
$BODY$
DECLARE
BEGIN
    PERFORM lock_ns_tree(OLD.tree);
-- Убираем разрыв в ключах и сдвигаем дочерние узлы:
   UPDATE ns_tree
        SET left_key = CASE WHEN left_key < OLD.left_key
                            THEN left_key
                            ELSE CASE WHEN right_key < OLD.right_key
                                      THEN left_key - 1 
                                      ELSE left_key - 2
                                 END
                       END,
            "level" = CASE WHEN right_key < OLD.right_key
                           THEN "level" - 1 
                           ELSE "level"
                      END,
            parent_id = CASE WHEN right_key < OLD.right_key AND "level" = OLD.level + 1
                           THEN OLD.parent_id
                           ELSE parent_id
                        END,
            right_key = CASE WHEN right_key < OLD.right_key
                             THEN right_key - 1 
                             ELSE right_key - 2
                        END,
            _trigger_lock_update = TRUE
        WHERE (right_key > OLD.right_key OR
            (left_key > OLD.left_key AND right_key < OLD.right_key)) AND
            tree = OLD.tree;
    RETURN OLD;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE
  COST 100;
ALTER FUNCTION ns_tree_after_delete_2_func() OWNER TO user;

CREATE TRIGGER ns_tree_after_delete_2_tr
    AFTER DELETE
    ON ns_tree
    FOR EACH ROW
    EXECUTE PROCEDURE ns_tree_after_delete_2_func();
    

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

• Композитный не уникальный на поля (left_key, right_key, level, tree);
• Не уникальный на поле (parent_id);

Наслаждайтесь ;-)