Краткий обзор методов хранения деревьев в БД
Если кратко, то:
- AL — когда у нас родитель хранится в колонке типа parent_id: »1»
- MP — полный путь до элемента хранится в колонке типа path: »1.2.5»
- NS [2, 3] — пара колонок lft и rgt, хранящие диапазон всех вложенных элементов, например, корень дерева из 9 элементов будет иметь левое значение »1», а правое — »18»
Более подробно см. у тов. Mikhus [1].
MySQL и рекурсия
В случае MySQL мы имеем рекурсию, но только на уровне хранимых процедур да и то до 255 уровней. Также мы можем задействовать рекурсию в связке язык программирования + БД, но число запросов здесь может быть потрясающим. Лучше делать всё в базе.
Погуглив мы узнаём, что любую рекурсивную задачу можно решить без неё родимой [4]. Задавшись подобным вопросом мы можем попробовать и… у нас получится! Ниже мы представляем вашему вниманию функцию rebuild_nested_set_tree, которая заполняет lft и rgt, зная parent_id.
Функция заполнения дерева без рекурсии
Для простоты представим, что у нас в табличке только одно дерево и в нём 8 элементов. На вход функция будет получать ничего. Естественно в production-версии мы будем на вход получать некие id вершин деревьев, которые будем учитывать в логике. Ниже мы приведём только тело функции для экономии места, а полный текст и запросы смотрите на SQLFiddle (спасибо тов. grokru за открытие этого сервиса).
-- Изначально сбрасываем все границы в 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);
Что мы здесь делаем?
В общем и целом мы находим крайний левый верхний элемент с заполненными границами и незаполненными детьми, вычисляем длину ряда его детей, обновляем границы элементов, которые справа от нас и затем уже обновляем границы его детей. Всё это делается без рекурсии в бесконечном цикле, пока у нас не кончатся элементы без границ.
Визуализировать процесс нам поможет несложная презенташка:
Ссылки
- Иерархические структуры данных и Doctrine by Mikhus, на Хабре, 10 декабря 2008 — хорошо описаны устройства каждого из основных методов
- Trees in SQL by Joe Celko, at Intelligent Enterprise, October 20, 2000 (english) — что такое Nested Set, по сравнению с Adjacency List и как конвертнуть из второго в первый (Joe Celko — папа термина Nested Set)
- Storing Hierarchical Data in a Database by Gijs Van Tulder, at sitepoint.com, April 30, 2003 (english) — картинки для описания логики раздачи «левых» и «правых» индексов, а также описание конкретики работы с разными подходами
- Any recursive algorithm can be rewritten as an iterative algorithm … by community wiki & Kristopher Johnson, at stackoverflow.com, December 11, 2009 (english) — любой рекурсивный алгоритм может быть преобразован в итерационный со стэком
- Исходники функции rebuild_nested_set_tree by garex, at sqlfiddle.com, 25 ноября 2012 — создание таблицы с деревом, заполнение тестовыми данными и создание функции для переезда
- Nested set без рекурсии: визуализация by garex, at slideshare.net, 25 ноября 2012 — визуализация алгоритма в одном из циклов
ссылка на оригинал статьи http://habrahabr.ru/post/153861/
Добавить комментарий