Задача
Как удобно делать выборки из деревьев типа Nested Sets, и как не удобно им управлять. Как удобно управлять деревьями типа id->parent_id, но как не удобно и накладно использовать рекурсии при выборках. Понятно, что при использовании модулей для управления деревьями часть проблемы снимается, но при этом процесс работы с базой данных не совсем прозрачен т.е. для изменения данных мы используем одни методы, для изменения расположения узла в дереве — другие, плюс еще транзакции не помешали бы. Эту не стыковку можно решить двумя способами:
- Использовать для работы с таблицей хранимые процедуры, в которой объединить оба метода обновления (вставки, удаления);
- Использовать триггеры, для исключения вообще каких-либо нестандартных методов работы;
Первый способ неудобен тем, что при изменении структуры таблицы, нам потребуется еще изменять процедуру, а так же быть максимально внимательным, при работе с таблицей, что бы все изменения данных проходили через наши процедуры, а не прямыми запросами. Второй способ несколько утяжеляет тяблицу введением дополнительных булевых полей, а так же приходится делать некоторые «финты ушами», хотя позволяет добиться максимальной прозрачности работы.
Первый способ — в топку, тем более где-то интернетах уже есть подобное решение.
База данных — PostgreSQL.
Таблица
Итак, какие триггеры нам понадобятся:
- До вставки записи — для формирования разрыва в дереве и ключей для создаваемого узла;
- До обновления — для перестроения дерева и формирования ключей для обновляемого узла;
- После удаления — удаление разрыва в дереве оставшееся после удаления узла;
Грабли:
- На время работы триггеров, требуется лочить таблицу, или отдельное дерево, если у нес в одной таблице деревьев несколько;
- В PostgreSQL и MySQL в триггерах нельзя отключить рекурсию, вот так;
Пункт второй подробнее: В триггере до обновления, могут обновляться записи из той же таблицы, что повлечет за собой повторый вызов триггера и так далее, так же и для триггера, вызываемого после удаления. Для того что бы понять вызван у нас запрос из триггера или нет, введем два дополнительных булевых поля, которые мы будем передавать в запросе как параметр (флаг) для триггера, а не как данные. Почему именно два — расскажу позднее.
Структуру таблицы сформируем сразу с учетом того, что у нас в ней будет храниться несколько деревьев. Объясню почему. Мне смешно до слез слушать глупых разработчиков, которые с пеной у рта доказывают, что мол, ай-ай-ай, при большом количестве узлов обновление узлов может затронуть все дерево, и это так тяжело для базы. Да, именно так. Не спорю. Только вот у меня еще ниразу не было огромного количества узлов в одном дереве потому, что:
- я не использую общий корневой узел;
- я разделяю деревья по узлам нулевого уровня;
Пример: Есть некоторый форум. В разделе форума 1’000 постов, у каждого поста 1’000 комментариев. Всего комментариев — 1’000’000. Так вот, раздел форума — НЕ является корневым узлом комментариев, так же как и посты НЕ являются узлами одного дерева, а являются только разделителями деревьев. В итоге, у меня 1’000 раздельных деревьев по 1’000 комментариев. Обновление происходит только лишь в пределах максимум 1’000 записей. В некоторых случаях, если и этого много, разделителем деревьев являются комментарии первого уровня. В итоге, перестроение дерева не является такой уж нагрузкой на базу. Изучайте мат часть.
Не будем о грустном, структура таблицы:
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, являются нашими вспомогательными полями.
Сразу сделаем функцию блокирующую дереве на изменение, пока транзакция не закончена:
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;
- Добавление в конец дерева, тогда нам не требуется ничего дополнительно передавать;
В такой же последовательности мы будем определять место назначения создаваемого узла.
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 как об управляющем параметре для триггера).
Алгоритм простой: сначала координаты перемещения, потом перестраиваем дерево.
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;
- Удаляем дочерние узлы;
- Удаляем разрыв в ключах в дереве (перестаиваем дерево);
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();Во втором решении просто смещаем дочернее дерево на уровень вверх, и удаляем разрыв ключей.
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);
Наслаждайтесь 😉