====== 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//);