Строим Nested Set дерево без рекурсии

Источник: habrahabr

garex

Деревья в базах данных можно хранить тремя основными методами: Adjacency List, Matherialized Path & Nested Set. Когда мы хотим переехать с AL на NS, это можно сделать с помощью рекурсии (если БД расово верная). Но что делать в случае MySQL?

Краткий обзор методов хранения деревьев в БД

Если кратко, то:

AL - когда у нас родитель хранится в колонке типа parent_id: ''1''
MP - полный путь до элемента хранится в колонке типа path: ''1.2.5''
NS ^[2, 3] - пара колонок lft и rgt, хранящие диапазон всех вложенных элементов, например, корень дерева из 9 элементов будет иметь левое значение ''1'', а правое - ''18''

MySQL и рекурсия

В случае MySQL мы имеем рекурсию, но только на уровне хранимых процедур да и то до 255 уровней. Также мы можем задействовать рекурсию в связке язык программирования + БД, но число запросов здесь может быть потрясающим. Лучше делать всё в базе.

Погуглив мы узнаём, что любую рекурсивную задачу можно решить без неё родимой ^[4]. Задавшись подобным вопросом мы можем попробовать и… у нас получится! Ниже мы представляем вашему вниманию функцию rebuild_nested_set_tree, которая заполняет lft и rgt, зная parent_id.

Функция заполнения дерева без рекурсии

Для простоты представим, что у нас в табличке только одно дерево и в нём 8 элементов. На вход функция будет получать ничего. Естественно в production-версии мы будем на вход получать некие id вершин деревьев, которые будем учитывать в логике. Ниже мы приведём только тело функции для экономии места, а полный текст и запросы смотрите на SQLFiddle (спасибо тов. grokru за открытие этого сервиса).

Исходник тела функции rebuild_nested_set_tree

-- Изначально сбрасываем все границы в NULL
UPDATE tree t SET lft = NULL, rgt = NULL;

-- Устанавливаем границы корневым элементам
SET @i := 0;
UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1)
WHERE t.parent_id IS NULL;

forever: LOOP
    -- Находим элемент с минимальной правой границей -- самый левый в дереве
    SET @parent_id := NULL;
    SELECT t.id, t.rgt FROM tree t, tree tc
    WHERE t.id = tc.parent_id AND tc.lft IS NULL AND t.rgt IS NOT NULL
    ORDER BY t.rgt LIMIT 1 INTO @parent_id, @parent_right;

    -- Выходим из бесконечности, когда у нас уже нет незаполненных элементов
    IF @parent_id IS NULL THEN LEAVE forever; END IF;

    -- Сохраняем левую границу текущего ряда
    SET @current_left := @parent_right;

    -- Вычисляем максимальную правую границу текущего ряда
    SELECT @current_left + COUNT(*) * 2 FROM tree
    WHERE parent_id = @parent_id INTO @parent_right;

    -- Вычисляем длину текущего ряда
    SET @current_length := @parent_right - @current_left;

    -- Обновляем правые границы всех элементов, которые правее
    UPDATE tree t SET rgt = rgt + @current_length
    WHERE rgt >= @current_left ORDER BY rgt;

    -- Обновляем левые границы всех элементов, которые правее
    UPDATE tree t SET lft = lft + @current_length
    WHERE lft > @current_left ORDER BY lft;

    -- И только сейчас обновляем границы текущего ряда
    SET @i := (@current_left - 1);
    UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1)
    WHERE parent_id = @parent_id ORDER BY id;
END LOOP;

-- Возвращаем самый самую правую границу для дальнейшего использования
RETURN (SELECT MAX(rgt) FROM tree t);

Что мы здесь делаем?

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

Визуализировать процесс нам поможет несложная презенташка:

Ссылки и changelog