Пользователь
0,1
рейтинг
25 ноября 2012 в 21:47

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

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

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


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

Более подробно см. у тов. Mikhus [1]. Также существует ещё один метод Closure Table, на что указал тов. resurection, но мы его пока в тренд не будем записывать.

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);

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


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

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



Ссылки


  1. Иерархические структуры данных и Doctrine by Mikhus, на Хабре, 10 декабря 2008 — хорошо описаны устройства каждого из основных методов
  2. Trees in SQL by Joe Celko, at Intelligent Enterprise, October 20, 2000 (english) — что такое Nested Set, по сравнению с Adjacency List и как конвертнуть из второго в первый (Joe Celko — папа термина Nested Set)
  3. Storing Hierarchical Data in a Database by Gijs Van Tulder, at sitepoint.com, April 30, 2003 (english) — картинки для описания логики раздачи «левых» и «правых» индексов, а также описание конкретики работы с разными подходами
  4. Any recursive algorithm can be rewritten as an iterative algorithm ... by community wiki & Kristopher Johnson, at stackoverflow.com, December 11, 2009 (english) — любой рекурсивный алгоритм может быть преобразован в итерационный со стэком
  5. Исходники функции rebuild_nested_set_tree by garex, at sqlfiddle.com, 25 ноября 2012 — создание таблицы с деревом, заполнение тестовыми данными и создание функции для переезда
  6. Nested set без рекурсии: визуализация by garex, at slideshare.net, 25 ноября 2012 — визуализация алгоритма в одном из циклов


Changelog


  1. Добавлено упоминание об ещё одном методе — Closure Table
  2. В исходных данных опечатка поправлена («Клёш» д.б. под «Брюками»)
  3. Из тела функции убран изврат с having min и заменён на адекватный order by с limit 1 (но функция всё равно работала правильно, т.к. двигала все правые элементы — это я уже позже удивился)
Александр @garex
карма
10,5
рейтинг 0,1
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (20)

  • +4
    Из статьи узнал о конструкции HAVING без GROUP BY
    • +4
      Но тут фишка в том, что конструкция `HAVING MIN(t.rgt)` работает не так, как автор считает. И ему просто повезло, что записи с минимальным t.rgt идут первыми.

      Потому лучше увиденную конструкцию забыть и не вспоминать :-)

      ps: а пользоваться ORDER BY + LIMIT 1

      pps: в подавляющем большинстве популярных субд (постгре, sql server, оракл) запрос автора будет считаться некорректным и даже не выполнится.
      • 0
        Спасибо. Теперь многие не только узнал о существовании такой конструкции, но и то, что лучше о ней не знать :)
  • 0
    Nested sets не единственное и не всегда самое лучшее решение.
    www.slideshare.net/billkarwin/sql-antipatterns-strike-back (см. 77 слайд, а лучше с 48, а ещё лучше с самого начала и до конца)
    • 0
      Никто и не утверждает, что лучшее и единственное. Касательно таблички на 77 слайде мы видим, что объединив AL с NS мы получаем вообще нечто идеальное, только обновление ужасное. Closure Table я не учел, но про него уже была на хабре дискуссия @ habrahabr.ru/post/67722/ и я склоняюсь к тому, что держать всех родителей на каждую запись — ужас тихий, особенно на глубоких случаях. Но опять же статья не про выбор способа, а про переход с одного из них на другой.
    • 0
      На хабре о Closure Table тоже писали habrahabr.ru/post/138947/
  • 0
    А как, и почему работает:

    > HAVING MIN(t.rgt)

    ?

    Объясните, пожалуйста.
    • 0
      Вы же уже отписали выше — как order by с limit 1 :)

      Это изврат нестандартный: dev.mysql.com/doc/refman/5.0/en/server-sql-mode.html#sqlmode_only_full_group_by

      SET @@SESSION.sql_mode = 'ONLY_FULL_GROUP_BY';

      И оно ломается.

      Лучше поправить на order by limit 1.
      • 0
        Тут дело в другом. вместо MIN(t.rgt) вы могли написать хоть AVG(42) и оно работало бы точно так же :-)

        Т.е. я говорил не о том, что оно совершенно не дружит со стандартами, а о том, что в случае использования конструкции HAVING любая_агрегирущюая_функция(с_любым_аргументом_кроме_NULL) всегда будет возвращаться первая строка резалт сета.

        Т.е. с MAX(t.rgt) вернётся тот же самый результат.
        • +1
          Да-да — я это уже понял щас. В процессе изобретения у меня для поиска левейшего элемента разные варианты запросов были — этот скорее всего пережил прочих :)

          ps: Я уже заменил на order с limit`ом
  • 0
    У меня mySQL 5.5.9, выдает ошибку:

    Ошибка
    SQL-запрос:
    forever: LOOP-- Находим элемент с минимальной правой границей — самый левый в дереве
    SET @parent_id := NULL;
    Ответ MySQL:
    #1064 — You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'forever: LOOP
    — Находим элемент с минимальной п' at line 1

    Что может быть? Может я зря запускаю этот запрос в phpMyAdmin?
    • 0
      У меня 5.5.22-0ubuntu1. Скорее всего phpMyAdmin DELIMITER`ы не уважает.

      Лучше тестить на sqlfiddle.com/#!2/7e58b/3 либо в инструменте другом, который с разделителями дружит.
      Либо отдельно в phpMyAdmin создать функцию, а потом её вызвать.
      Народ, кто с phpMyAdmin`ом дружит, подскажите чё каво?
      • 0
        Взял код из sqlfiddle и поставил разделителями //
        тогда заработало. Очень удобная функция, чтобы избавить PHP от мучений.
  • 0
    А как бы это можно было бы на Postgres Sql сделать?
    У большинства хостеров есть Posgres — и как правило, mysql и postgres совместимы в основном.
    • 0
      Х.з. — скорее всего также большей частью. Но т.к. постгрес более расово верная бд — там вообще м.б. так не надо делать и рекурсивными запросами/функциями можно обойтись.

      Но для прикола можно на SQLfiddle попробовать сменить тип БД и поиграться. Я в постгре пока не очень в тонкостях. Кто хорошо — подскажите.
  • 0
    Справедливости ради, то что ТС назвал AL есть ли частный и самый простой случай AL. Closure tables — это его более продвинутая версия. Причем, при грамотном приготовлении она является гораздо более эффективной, чем MP или NS. Нет такого раздутого требования и ограничений у путей и нет такого дикого оверхеда при изменениях как в NS, когда изменение одного узла может повлечь апдейт практически всей таблицы.
    • 0
      Справедливости ради, то что ТС назвал AL есть лишь частный и самый простой случай AL.

      Единственно мне в этом варианте не нравится «жёппа», когда у нас уровень вложенности большой и элементов на листьях много. Но хотя это только при вставке. Удаление же у нас само за собой подчищает?

      ps: автор коммента имел в виду «есть лишь»
      • 0
        Вероятность, что вставляется сразу сто уровней редка. Но даже в таком случае, поскольку AL лежит в отдельной таблице, это минимальное число IO-операций. По сути даже вставка этих ста уровней поместилась бы в одну страницу БД. Если же представить себе материализованные пути, где в каждой записи надо резервировать место под эти 100 уровней, то вот это и называется «жёппа». И да, удаление работает.
  • +1
    храню каталог методом AL, вытягиваю весь каталог по SELECT * и сторю дерево на клиенте. Быстро и дешево.
    В случае с NS — проблемы во вставками и передвижками веток. геморно…
    • 0
      У каждого способа свои плюсы. У нас на работе деревья в 500кк узлов и надо быстро собирать аналитику по узлам — только NS дал более менее приемлемую скорость.

      С другой стороны по AL очень просто выводить деревья (особенно если у тебя есть PostgreSQL, Oracle или ещё что-то соизмеримого калибра с их синтаксисом WITH… AS или START WITH… CONNECT BY ...)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.