Вывод дерева mysql

#mysql #sql #дерево

Есть таблица elements следующей структуры Adjacency List Model:

id parent index


Где index - это порядок элемента.
Нужно одним запросом сформировать путь, получающийся при обходе в глубину.
То есть если у нас такой вид:

1 0 1
2 0 2
3 1 1
4 1 2
5 2 1
6 0 3


То выведется
1 3 4 2 5 6

Нужно на чистом mysql без использования php и тд.
Заранее спасибо

P.S. Менять в структуре, к сожалению, ничего нельзя

Заранее спасибо
    

Ответы

Ответ 1

В MySQL нет штатных средств для работы с рекурсивными запросами. Но как известно,
если очень хочется, то можно (хотя выглядит это жутковато и оптимизации по скорости
это не поддается):

select id,path
  from (
   select  @path:=if(@id!=id,`index`,
             coalesce(
               (select concat(`index`,'/',@path)
                  from Tree1 where id=@pid)
             ,@path)
           ) path,
           @pid:=if(@id!=id,parent,
             (select parent from Tree1 N
               where id=@pid)
             ),
            @id:=id id, N
     from Tree1 T,
          (select @n:=@n+1 N
             from Tree1,(select @n:=0) N limit 3) Seq,
          (select @id:=0,@path:='') X
    order by id, N
  ) X
 where N=3
 order by path


Так как ни рекурсии ни циклов в обычном смысле слов нет, то запрос эмулирует рекурсию
с помощью эмуляции цикла. В качестве цикла используется склейка с любой таблицей, в
которой записей не менее, чем максимально возможный уровень иерархии в дереве. В данном
примере используется выборка из той же самой таблицы, явно ограниченная limit 3 (если
вложенность дерева больше - число надо соответственно увеличить). Собственно данные
из этой таблицы не берутся, а создаются порядковые номера (N).

После этой склейки у нас в выборке появляется по 3 записи с одним и тем же id. На
каждой из них, с помощью переменных, мы получаем id очередной родительской ветки, углубляясь
по дереву (так как переменные помнят значения, сформированные в предыдущей строке).
Самое главное, что мы тут формируем это путь к данной записи в виде индексов сортировки
(если index может быть более 9 то для правильной сортировки надо выравнивать его в
пути до одинаковой длины с помощью lpad())

В какой то момент записи родителей заканчиваются, мы дошли до корня дерева, тогда
подзапрос индекса родителя возвращает NULL и при этом с помощью coalesce мы сохраняем
ранее сформированный путь. Таким образом в последней записи нашего "цикла" у нас гарантированно
будет полный путь до данного листа дерева. Нам остается только убрать из выборки рабочие
строки цикла с частично сформированными путями, т.е. выбрать только последние строки
(where N=3) и отсортировать по пути индексов.


Ответ 2

Чтобы вывести полный путь в одном запросе нужно использовать Nested Set Model. (Полная
информация по ссылке)


  Для построения пути можно использовать хранимую функцию. При
  процедурном языке мы можем начать в нижней части дерева и перебирать
  вверх, чтобы вернуть полное дерево или единственный путь.


https://web.archive.org/web/20110606032941/http://dev.mysql.com/tech-resources/articles/hierarchical-data.html