Задача
Задача такая же как и в предыдущей статье, только применимо к MySQL.
Грабли
Хорошая новость ребята! В MySQL нет проблемы с рекурсивными триггерами! Разработчики MySQL просто тупо лочат изменяемую таблицу даже на уровне триггера, вот редиски. Но, собственно, нас может остановить только отключение электричества.
Есть небольшая лазейка, с… объединенными таблицами. Хотя я не нашел в документации подтверждения того, что это так специально было задумано, но и отрицания тоже не было. Правда есть вероятность того, что эту лазейку могут прикрыть, хотя я не вижу в этом смысла.
Увы, механизм триггеров в MySQL новый и довольно сырой, что накладывает некоторые ограничения на его использование, но все же его достаточно для решения нашей задачи.
Итак, исходная таблица:
SQL код (1)
CREATE TABLE `ns_tree` (
`id` int(11) NOT NULL auto_increment,
`left_key` int(11) NOT NULL default '0',
`right_key` int(11) NOT NULL default '0',
`level` int(11) NOT NULL default '0',
`parent_id` int(11) NOT NULL default '0',
`tree` int(11) NOT NULL default '1',
`field1` text,
PRIMARY KEY (`id`)
) ENGINE=MyISAM;
На основе нее делаем точно такую же таблицу, с точно таким же набором полей:
SQL код (2)
CREATE TABLE `_ns_tree` (
`id` int(11) NOT NULL auto_increment,
`left_key` int(11) NOT NULL default '0',
`right_key` int(11) NOT NULL default '0',
`level` int(11) NOT NULL default '0',
`parent_id` int(11) NOT NULL default '0',
`tree` int(11) NOT NULL default '1',
`field1` text,
PRIMARY KEY (`id`)
) ENGINE=MERGE INSERT_METHOD=LAST UNION=(`ns_tree`);
Ключевое слово — MERGE по сути мы создаем представление нашей таблицы, с которым мы можем работать как с таблицей. Вообще механизм MERGE тоже немного сыроват. Структура объединенной таблицы должна быть точно такой же как исходной.
ВАЖНО!!! При изменении структуры исходной таблицы связь между таблицами — теряется, а вот между уже связанными строками — НЕТ! Будьте внимательны. При изменении структуры исходной таблицы обязательно это же изменение применить и к объединенной!
Так же исходная таблица должна быть MyISAM, оно и понятно, транзакции в этом случае не применимы ввиду того, что таблицы не могут друг друга лочить, а данные в них одни и те же. Впрочем, для нас это не страшно, так как в пределах триггера исходная таблица будет залочена, а изменение данных объединенной таблицы мы будем производить из триггеров, поэтому пересечений запросов быть не может.
Еще, на что хотел обратить внимание: Настоятельно рекомендую не использовать корневые узлы в пределах одного дерева (о чем я говорил в предыдущей статье), так как таблица блокируется полностью, и может формироваться слишком длинная очередь.
Создание записи
MySQL диалект триггеров несколько отличается от диалекта PostgreSQL:
- Не обязательно объявлять переменные в начале процедуры;
- Прервать выполнение триггера нельзя, он должен отработать полностью;
- Как было сказано выше, рекурсии мы не боимся, поэтому лишние проверки и дополнительные поля нам не потребуются;
- Переменные появляются по ходу кода;
- Вместо возвратов из триггера, оборачиваем код условиями;
- Все изменения, касающиеся структуры дерева, применяем к вспомогательной объединенной таблице;
CREATE DEFINER = 'user'@'localhost' TRIGGER `ns_tree_before_ins_tr` BEFORE INSERT ON `ns_tree`
FOR EACH ROW
BEGIN
SET @left_key := 0;
SET @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
SET NEW.parent_id := @tmp_parent_id;
SET @left_key := NEW.left_key;
SET @level := @tmp_level;
ELSEIF @tmp_left_key IS NOT NULL AND @tmp_left_key > 0 AND NEW.left_key = @tmp_right_key THEN
SET NEW.parent_id := @tmp_id;
SET @left_key := NEW.left_key;
SET @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
SET @left_key := 1;
END IF;
SET @level := 0;
SET NEW.parent_id := 0;
END IF;
-- Устанавливаем новые значения ключей
SET NEW.left_key := @left_key;
SET NEW.right_key := @left_key + 1;
SET NEW.`level` := @level;
-- Формируем разрыв в дереве
UPDATE _ns_tree
SET left_key = CASE WHEN left_key >= @left_key
THEN left_key + 2
ELSE left_key + 0
END,
right_key = right_key + 2
WHERE tree = NEW.tree AND right_key >= @left_key;
END;
Изменение записи
Принцип тот же с применением диалекта.
SQL код (4)
CREATE DEFINER = 'user'@'localhost' TRIGGER `ns_tree_before_upd_tr` BEFORE UPDATE ON `ns_tree`
FOR EACH ROW
BEGIN
-- Запрещаем изменять поля, или присылать гадости
SET NEW.tree := OLD.tree;
SET NEW.right_key := OLD.right_key;
SET NEW.`level` := OLD.`level`;
SET @return_flag := 0;
IF NEW.parent_id IS NULL THEN SET NEW.parent_id := 0; END IF;
-- Проверяем, а есть ли изменения связанные со структурой дерева
IF NEW.parent_id <> OLD.parent_id OR NEW.left_key <> OLD.left_key THEN
-- Дерево таки перестраиваем, что ж, приступим:
SET @left_key := 0;
SET @level := 0;
SET @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;
SET @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
SET NEW.parent_id := OLD.parent_id;
SET NEW.left_key := OLD.left_key;
SET @return_flag := 1;
END IF;
END IF;
-- Если не parent_id, то изменен 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
SET NEW.parent_id := @tmp_parent_id;
SET @left_key := NEW.left_key;
SET @level := @tmp_level;
ELSEIF @tmp_left_key IS NOT NULL AND
@tmp_left_key > 0 AND
NEW.left_key = @tmp_right_key THEN
SET NEW.parent_id := @tmp_id;
SET @left_key := NEW.left_key;
SET @level := @tmp_level + 1;
ELSEIF NEW.left_key = 1 THEN
SET NEW.parent_id := 0;
SET @left_key := NEW.left_key;
SET @level := 0;
ELSE
SET NEW.parent_id := OLD.parent_id;
SET NEW.left_key := OLD.left_key;
SET @return_flag = 1;
END IF;
END IF;
-- Теперь мы знаем куда мы перемещаем дерево
-- Проверяем а стоит ли это делать
IF @return_flag IS NULL OR @return_flag = 0 THEN
SET @skew_level := @level - OLD.`level`;
IF @left_key > OLD.left_key THEN
-- Перемещение вверх по дереву
SET @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
WHERE tree = OLD.tree AND
right_key > OLD.left_key AND
left_key < @left_key AND
id <> OLD.id;
SET @left_key := @left_key - @skew_tree;
ELSE
-- Перемещение вниз по дереву:
SET @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
WHERE tree = OLD.tree AND
right_key >= @left_key AND
left_key < OLD.right_key AND
id <> OLD.id;
END IF;
-- Дерево перестроили, остался только наш текущий узел
SET NEW.left_key := @left_key;
SET NEW.`level` := @level;
SET NEW.right_key := @left_key + @skew_tree - 1;
END IF;
END IF;
END;
ВНИМАНИЕ!!! В MySQL имеет значение порядок перечисления полей в запросе UPDATE, так как поля изменяемые во время запроса в самом же запросе меняют значение на новое, поэтому, если мы дальше по запросу используем эти поля в условиях, результат будет неадекватным.
Удаление записи
Из-за отсутствия проблем с рекурсией триггеров, удаление вообще становится тривиальной задачей.
Триггер для варианта: «удаление ветки целиком»:
SQL код (5)
CREATE DEFINER = 'user'@'localhost' TRIGGER `ns_tree_before_del_tr` AFTER DELETE ON `ns_tree`
FOR EACH ROW
BEGIN
-- Удаляем дочерние узлы:
DELETE FROM _ns_tree
WHERE
tree = OLD.tree AND
left_key > OLD.left_key AND
right_key < OLD.right_key;
-- Убираем разрыв в ключах:
SET @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
WHERE right_key > OLD.right_key AND
tree = OLD.tree AND
id <> OLD.id;
END;
Триггер для варианта: «удаление узла со смещением дочерних узлов на уровень ввверх»:
SQL код (6)
CREATE DEFINER = 'user'@'localhost' TRIGGER `ns_tree_before_del_tr` AFTER DELETE ON `ns_tree`
FOR EACH ROW
BEGIN
-- Убираем разрыв в ключах:
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,
parent_id = CASE WHEN right_key < OLD.right_key AND `level` = OLD.level + 1
THEN OLD.parent_id
ELSE parent_id
END,
`level` = CASE WHEN right_key < OLD.right_key
THEN `level` - 1
ELSE `level`
END,
right_key = CASE WHEN right_key < OLD.right_key
THEN right_key - 1
ELSE right_key - 2
END
WHERE (right_key > OLD.right_key OR
(left_key > OLD.left_key AND right_key < OLD.right_key)) AND
tree = OLD.tree;
END;
Хочу обратить внимание на то, что изменения затрагивающие структуру дерева нужно производить не пачками, а последовательно для каждого узла, что бы сохранялась его целостность.
Собственно все. Осталось только проставить индексы (мне опять же лениво сюда писать SQL команды, поэтому просто их озвучу):
- Композитный не уникальный на поля (left_key, right_key, level, tree);
- Не уникальный на поле (parent_id);
Наслаждайтесь ;-)
Сергей Томулевич aka Phoinix (08.07.2009 г.)
