Различия

Здесь показаны различия между двумя версиями данной страницы.

--- postgres:nested_set [2024/11/02 10:05]
werwolf создано
+++ postgres:nested_set [2024/11/02 10:07] (текущий)
werwolf
@@ Строка 1: / Строка 1: @@
-tet
+====== 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)
+<code sql>
+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)
+);
+</code>
+Собственно — //_trigger_lock_update// и //_trigger_for_delete//, являются нашими вспомогательными полями.Сразу сделаем функцию блокирующую дереве на изменение, пока транзакция не закончена: SQL код (2)
+<code sql>
+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;
+</code>
+=== Создание записи ===
+У нас есть 3 варианта добаления узла в дерево:
+  * Добавление в подчинение определенному узлу, тогда мы передаем //parent_id//;
+  * Добавление в определенную точку дерева, тогда мы передаем //left_key//;
+  * Добавление в конец дерева, тогда нам не требуется ничего дополнительно передавать;
+В такой же последовательности мы будем определять место назначения создаваемного узла. SQL код (3)
+<code sql>
+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();
+</code>
+Теперь некоторые пояснения:
+  * //_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)
+<code sql>
+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();
+</code>
+Пояснения:
+  * Изначально, кроме параметра //_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)
+<code sql>
+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();
+</code>
+Во втором решении просто смещаем дочернее дерево на уровень вверх, и удаляем разрыв ключей. SQL код (6)
+<code sql>
+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();
+</code>
+Собственно все. Осталось только проставить индексы (мне лениво сюда писать SQL команды, поэтому просто их озвучу):
+  * Композитный не уникальный на поля (//left_key, right_key, level, tree//);
+  * Не уникальный на поле (//parent_id//);

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы