- PVSM.RU - https://www.pvsm.ru -
Деревья в базах данных можно хранить тремя основными методами: Adjacency List, Matherialized Path & Nested Set. Когда мы хотим переехать с AL на NS, это можно сделать с помощью рекурсии (если БД расово верная). Но что делать в случае MySQL?
Если кратко, то:
Более подробно см. у тов. Mikhus [3] [1 [4]].
В случае MySQL мы имеем рекурсию, но только на уровне хранимых процедур да и то до 255 уровней [5]. Также мы можем задействовать рекурсию в связке язык программирования + БД, но число запросов здесь может быть потрясающим. Лучше делать всё в базе.
Погуглив мы узнаём, что любую рекурсивную задачу можно решить без неё родимой [4 [6]]. Задавшись подобным вопросом мы можем попробовать и… у нас получится! Ниже мы представляем вашему вниманию функцию rebuild_nested_set_tree, которая заполняет lft и rgt, зная parent_id.
Для простоты представим, что у нас в табличке только одно дерево и в нём 8 элементов. На вход функция будет получать ничего. Естественно в production-версии мы будем на вход получать некие id вершин деревьев, которые будем учитывать в логике. Ниже мы приведём только тело функции для экономии места, а полный текст и запросы [7] смотрите на SQLFiddle (спасибо тов. grokru [8] за открытие этого сервиса).
-- Изначально сбрасываем все границы в 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
HAVING MIN(t.rgt) 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);
В общем и целом мы находим крайний левый верхний элемент с заполненными границами и незаполненными детьми, вычисляем длину ряда его детей, обновляем границы элементов, которые справа от нас и затем уже обновляем границы его детей. Всё это делается без рекурсии в бесконечном цикле, пока у нас не кончатся элементы без границ.
Визуализировать процесс нам поможет несложная презенташка:
Автор: garex
Источник [15]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/mysql/21025
Ссылки в тексте:
[1] 2: #ref2
[2] 3: #ref3
[3] Mikhus: http://habrahabr.ru/users/mikhus/
[4] 1: #ref1
[5] до 255 уровней: http://dev.mysql.com/doc/refman/5.5/en/server-system-variables.html#sysvar_max_sp_recursion_depth
[6] 4: #ref4
[7] полный текст и запросы: http://sqlfiddle.com/#!2/fd4ff/1
[8] grokru: http://habrahabr.ru/users/grokru/
[9] Иерархические структуры данных и Doctrine: http://habrahabr.ru/post/46659/
[10] Trees in SQL: http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html
[11] Storing Hierarchical Data in a Database: http://www.sitepoint.com/hierarchical-data-database/
[12] Any recursive algorithm can be rewritten as an iterative algorithm ...: http://stackoverflow.com/a/1888735/388929
[13] garex: http://habrahabr.ru/users/garex/
[14] Nested set без рекурсии: визуализация: http://www.slideshare.net/ustimenko-alexander/nested-set
[15] Источник: http://habrahabr.ru/post/153861/
Нажмите здесь для печати.