mysql:nested_set []

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
====== Nested Sets + MySQL TRIGGER ======


=== Грабли ===

\\ Хорошая новость ребята! В //MySQL// нет проблемы с рекурсивными триггерами! Разработчики //MySQL// просто тупо лочат изменяемую таблицу даже на уровне триггера, вот редиски. Но, собственно, нас может остановить только отключение электричества.\\ Есть небольшая лазейка, с… объединенными таблицами. Хотя я не нашел в документации подтверждения того, что это так специально было задумано, но и отрицания тоже не было. Правда есть вероятность того, что эту лазейку могут прикрыть, хотя я не вижу в этом смысла.\\ Увы, механизм триггеров в //MySQL// новый и довольно сырой, что накладывает некоторые ограничения на его использование, но все же его достаточно для решения нашей задачи.\\ Итак, исходная таблица:\\ SQL код (1)

<code mysql>
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;
</code>

\\ На основе нее делаем точно такую же таблицу, с точно таким же набором полей:\\ SQL код (2)

<code mysql>
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`);
</code>

\\ Ключевое слово — //MERGE// по сути мы создаем представление нашей таблицы, с которым мы можем работать как с таблицей. Вообще механизм MERGE тоже немного сыроват. Структура объединенной таблицы должна быть точно такой же как исходной.\\ **ВАЖНО!!! При изменении структуры исходной таблицы связь между таблицами — теряется, а вот между уже связанными строками — НЕТ! Будьте внимательны. При изменении структуры исходной таблицы обязательно это же изменение применить и к объединенной!**\\ Так же исходная таблица должна быть MyISAM, оно и понятно, транзакции в этом случае не применимы ввиду того, что таблицы не могут друг друга лочить, а данные в них одни и те же. Впрочем, для нас это не страшно, так как в пределах триггера исходная таблица будет залочена, а изменение данных объединенной таблицы мы будем производить из триггеров, поэтому пересечений запросов быть не может.\\ Еще, на что хотел обратить внимание: Настоятельно рекомендую не использовать корневые узлы в пределах одного дерева (о чем я говорил в предыдущей статье), так как таблица блокируется полностью, и может формироваться слишком длинная очередь.\\ \\ 

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

\\ //MySQL// диалект триггеров несколько отличается от диалекта //PostgreSQL//:\\ 

  * Не обязательно объявлять переменные в начале процедуры;
  * Прервать выполнение триггера нельзя, он должен отработать полностью;
  * Как было сказано выше, рекурсии мы не боимся, поэтому лишние проверки и дополнительные поля нам не потребуются;

Поэтому несколько изменяется логика:\\ 

  * Переменные появляются по ходу кода;
  * Вместо возвратов из триггера, оборачиваем код условиями;
  * Все изменения, касающиеся структуры дерева, применяем к вспомогательной объединенной таблице;

SQL код (3)

<code mysql>
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;
</code>

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

\\ Принцип тот же с применением диалекта.\\ SQL код (4)

<code mysql>
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;
</code>

\\ ВНИМАНИЕ!!! В MySQL имеет значение порядок перечисления полей в запросе //UPDATE//, так как поля изменяемые во время запроса в самом же запросе меняют значение на новое, поэтому, если мы дальше по запросу используем эти поля в условиях, результат будет неадекватным.\\ \\ 

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

\\ Из-за отсутствия проблем с рекурсией триггеров, удаление вообще становится тривиальной задачей.\\ Триггер для варианта: «удаление ветки целиком»:\\ SQL код (5)

<code mysql>
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;
</code>

\\ Триггер для варианта: «удаление узла со смещением дочерних узлов на уровень ввверх»:\\ SQL код (6)

<code mysql>
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;
</code>

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

  * Композитный не уникальный на поля (//left_key, right_key, level, tree//);
  * Не уникальный на поле (//parent_id//);
Инструменты пользователя

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

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