Пользователь
0,0
рейтинг
5 ноября 2008 в 10:44

Разработка → Иерархические (рекурсивные) запросы

SQL*
Дерево объектов

Чтобы понять рекурсию, сначала надо понять рекурсию. Возможно, поэтому рекурсивные запросы применяют так редко. Наверняка вы представляете что такое SQL-запрос, я расскажу, чем рекурсивные запросы отличаются от обычных. Тема получилась объемная, приготовьтесь к долгому чтению. В основном речь пойдет об Oracle, но упоминаются и другие СУБД.



Суть проблемы



Большинство современных СУБД (Система Управления Базами Данных) — реляционные, т.е. представляют данные в виде двумерной таблицы, в которой есть строки (записи) и столбцы (поля записей). Но на практике мы часто сталкиваемся с иной организацией данных, а именно иерархической.

Взгляните на список файлов на вашем компьютере: все они организованы в виде дерева. Аналогично можно представить книги в библиотеке: Библиотека->Зал->Шкаф->Полка->Книга. То же самое и статьи на сайте: Сайт->Раздел->Подраздел->Статья. Примеры можно приводить долго. Впрочем, тут еще можно разделить все на отдельные таблицы: таблица для хранения списка библиотек, другая таблица для списка залов, третья для шкафов и т.д. Но если заранее не известна глубина вложенности или эта вложенность может меняться, тут уж от иерархии никак не отмашешься.

Проблема в том, что данные, имеющие иерархическую структуру, очень плохо представляются в реляционной модели. В стандарте SQL-92 нет средств для их обработки.

Зато такие средства появились в стандарте SQL-1999. Правда к тому времени в Oracle уже был собственный оператор CONNECT BY. Несмотря на это, в SQL-1999 синтаксис рекурсивных запросов совершенно не похож на синтаксис CONNECT BY в Oracle и использует ключевое слово WITH. Реализация же рекурсивных запросов в других СУБД несколько запоздала, так в MS SQL Server она появилась лишь в версии 2005.

Так же как и в синтаксисе, есть отличия и в терминологии. В Oracle обычно обсуждаемые запросы называются “иерархические”, у всех остальных “рекурсивные”. Суть от этого не меняется, я буду использовать и то и другое.

От слов к делу!



Для демонстрации будем использовать структуру каталогов, нам потребуется тестовая таблица, состоящая из 3-х полей:
id – идентификатор,
pid – идентификатор родителя (ссылается на id другой записи в той же таблице),
title – название каталога (вместо него может быть что угодно, даже несколько полей или ссылок к другим таблицам).

create table test_table (
  id int,
  pid int,
  title varchar(256)
);


Здесь я использовал синтаксис mySQL, в других СУБД он несколько отличается. Так, в Oracle используются другие типы данных: вместо int — number, а вместо varchar — varchar2.

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

insert into test_table values (1, null, 'Россия');


Думаю, остальные строки заполнить не составит сложностей. Получается почти как на картинке, только не в том порядке. Я специально заполнял не по-порядку, чтобы простым SELECT * FROM test_table получалось не иерархическая структура:

  ID        PID TITLE
---- ---------- --------------------
   1            Россия
   2          1 Воронеж
   3          2 ООО "Рога и копыта"
   4          1 Москва
   5          1 Лиски
   6          3 Главный офис
   7          3 Офис 1
   8          3 Офис 2
   9          8 Сервер 1
  10          5 ЛискиПресс


Тестовые данные готовы. Приступим к выборкам.

mySQL



Вынужден огорчить пользователей mySQL – в этой СУБД придется рекурсию организовывать внешними по отношению к СУБД средствами, например на php (код приводить не буду, его публиковали не раз, например здесь, достаточно поискать по запросу “mySQL tree” и т.п.).

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

Как-то я выводил дерево объектов в действующем проекте на php. База данных была на mySQL. Поплевавшись на отсутствие удобных операторов, я решил тогда не отображать все дерево целиком, а показать пользователю только первый уровень (схлопнутое дерево). При клике по плюсику в узле дерева отображались дочерние узлы для выбранного объекта, при этом они подгружались через AJAX. Выборка дочерних узлов по известному pid происходит быстро, поэтому интерфейс получился вполне шустрым. Возможно, это не лучшее решение, но оно имеет право на жизнь.

SQL-1999



В отличие от предыдущего стандарта SQL-92, в названии следующего решили отобразить номер тысячелетия, чтобы он не страдал от проблемы двухтысячного года. Помимо этого :-), появились новые типы данных (LOB), новые предикаты SIMILAR и DISTINCT, точки сохранения транзакций, объекты и их методы, и многое другое. Среди нововведений появились также рекурсивные запросы, о которых мы сейчас и поговорим.

Для получения иерархических данных используется временное представление, которое описывается оператором WITH. После этого из нее выбираются данные простым селектом. В общем виде синтаксис примерно такой:

WITH [recursive] имя_алиаса_запроса [ (список столбцов) ]
AS (запрос) 
основной запрос


В MS SQL нет ключевого слова RECURSIVE, его следует опустить. Но в остальном все то же самое. Такой синтаксис поддерживается в DB2, Sybase iAnywhere, MS SQL, начиная с версии 2005, и во всех базах данных, которые поддерживают стандарт SQL 1999.

Тогда для получения нашего дерева запрос получится такой:

WITH RECURSIVE
 Rec (id, pid, title)
 AS (
   SELECT id, pid, title FROM test_table
   UNION ALL
   SELECT Rec.id, Rec.pid, Rec.title
    FROM Rec, test_table
    WHERE Rec.id = test_table.pid
   )
 SELECT * FROM Rec
 WHERE pid is null;


Здесь используется рекурсивная таблица Rec, которую мы сами придумали, построив ее по исходной таблице test_table. В описании Rec указано правило, каким образом соединять: WHERE Rec.id = test_table.pid. А в главном запросе отметили, что начинать надо с записи, у которой pid является пустым, т.е. с корневой записи.

Честно говоря, я никогда не работал в MS SQL Server 2005 или другой СУБД, использующей такой синтаксис. Поэтому написал этот запрос чисто из теоретических соображений. Для общности картины, чтобы было с чем сравнить.

В MS SQL 2008 можно применить более новое средство hierarchyid. Спасибо XaocCPS за его описание.

Oracle



Наконец-то мы добрались до Oracle! Об этой СУБД я хотел бы рассказать поподробнее. В Oracle иерархические запросы появились в 8-ой версии, задолго до появления стандарта. Поэтому до сих пор используется совсем другой синтаксис. Лично мне он кажется более понятным и напоминающим обычные функциональные языки. Хотя, скорее всего, это дело привычки.

Описание синтаксиса в документации напоминает бусы: на единую нить запроса нанизываются нужные операторы. Никому не приходило в голову сделать украшение для гички?

Структура операторов иерархического запроса в Oracle

Тут видно, что единственно важное условие для построения иерархического запроса – это оператор CONNECT BY, остальное “нанизывается” по мере надобности.

Необязательный оператор START WITH говорит Ораклу с чего начинать цикл, т.е. какая строка (или строки) будет корневой. Условие может быть практически любым, можно даже использовать функции или внутренние запросы: pid is null, или id = 1, или даже substr(title, 1, 1) = ‘Р’.

Условие после CONNECT BY нужно указать обязательно. Тут надо сказать Ораклу, как долго продолжать цикл. Что-то в духе while в обычных языках программирования. Например, мы можем попросить достать нам 10 строк: rownum<=10 – он и нафигачит нам в цикле ровно 10 одинаковых строк. Почему одинаковых? Да потому что мы указали какую строку выбрать первой, а как найти следующую нет – вот он и выдает 1-ую строку нужное количество раз. Кстати сказать, rownum это псевдостолбец, в котором нумеруются строки, начиная от 1 в порядке их выдачи. Его можно использовать не только в иерархических запросах. Но это уже другая история.

Как же получить нормальную иерархию? Нужно использовать специальный оператор, который называется PRIOR. Это обычный унарный оператор, точно такой же как + или -. “Позвоните родителям” – говорит он, заставляя Оракл обратиться к предыдущей записи. С его помощью можно написать правило pid = PRIOR id (или PRIOR id = pid, как говорится, от перестановки мест…).

Что получается? Оракл находит первую запись, удовлетворяющую условию в START WITH, и принимается искать следующую. При этом к той первой записи можно обратиться через PRIOR. Если мы все сделали правильно, то Оракл будет искать записи, в которых в поле для хранения информации о родителе (pid) будет содержаться значение, равное идентификатору id нашей первой записи. Таким образом будут найдены все потомки корневой записи. А так как процесс рекурсивный, аналогичный поиск будет продолжаться с каждой найденной строкой, пока не отыщутся все потомки.

Теперь у нас есть все необходимое, чтобы написать иерархический запрос в Oracle. Но прежде чем мы его напишем, расскажу еще об одной штуке. Порядок строк это хорошо, но нам было бы трудно понять, две строки рядом это родитель и его потомок или два брата-потомка одного родителя. Пришлось бы сверять id и pid. К счастью, Oracle предлагает в помощь дополнительный псевдостолбец LEVEL. Как легко догадаться, в нем записывается уровень записи по отношению к корневой. Так, 1-ая запись будет иметь уровень 1, ее потомки уровень 2, потомки потомков — 3 и т.д.

SELECT level, id, pid, title
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid;


LEVEL         ID        PID TITLE
------ ---------- ---------- -------------------
     1          1            Россия
     2          2          1 Воронеж
     3          3          2 ООО "Рога и копыта"
     4          6          3 Главный офис
     4          7          3 Офис 1
     4          8          3 Офис 2
     5          9          8 Сервер 1
     2          4          1 Москва
     2          5          1 Лиски
     3         10          5 ЛискиПресс


Неплохо. Все дочерние строки оказываются под своими родителями. Сортировку бы еще добавить, чтобы записи одного уровня выводились не абы-как, а по алфавиту. Ну чтож, сортировка это просто: добавим в конец запроса конструкцию ORDER BY title.

SELECT level, id, pid, title
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid
ORDER BY title;


LEVEL         ID        PID TITLE
------ ---------- ---------- -------------------
     2          2          1 Воронеж
     4          6          3 Главный офис
     2          5          1 Лиски
     3         10          5 ЛискиПресс
     2          4          1 Москва
     3          3          2 ООО "Рога и копыта"
     4          7          3 Офис 1
     4          8          3 Офис 2
     1          1            Россия
     5          9          8 Сервер 1


О, нет! Вся иерархия поломалась. Что же получилось? Оракл честно выбрал нужные строки в порядке иерархии (об этом говорит правильная расстановка level), а затем пересортировал их согласно правилу ORDER BY. Чтобы указать Ораклу, что сортировать надо только в пределах одного уровня иерархии, нам поможет маленькая добавка в виде оператора SIBLINGS. Достаточно изменить условие сортировки на ORDER SIBLINGS BY title – и все встанет на свои места.

Кстати, возможно все еще не понятно, почему этот порядок строк является деревом. Можно убрать все “лишние” поля и добавить отступы, станет более наглядно:

SELECT lpad(' ', 3*level)||title as Tree
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid
ORDER SIBLINGS BY title;


TREE
-----------------------------
   Россия
      Воронеж
         ООО "Рога и копыта"
            Главный офис
            Офис 1
            Офис 2
               Сервер 1
      Лиски
         ЛискиПресс
      Москва


Ну вот, теперь все в точности, как на картинке в самом начале статьи.

Помните, файловые менеджеры обычно пишут путь к каталогу, в котором вы находитесь: /home/maovrn/documents/ и т.п.? Неплохо было бы и нам сделать так же. А сделать это можно абсолютно не напрягаясь: специалисты из Oracle все уже сделали за нас. Просто берем и используем функцию SYS_CONNECT_BY_PATH(). Она принимает два параметра через запятую: название колонки и строку с символом-разделителем. Будем не оригинальны, напишем так: SYS_CONNECT_BY_PATH(title, ‘/’).

Заодно ограничим вывод, выбрав только одну строку. Для этого, как всегда, нужно добавить условие WHERE. Даже в иерархическом запросе ограничивающее условие применяется ко всем строкам. Вставить его надо до иерархической конструкции, сразу после FROM. Для примера определим путь до “Сервер 1”, который у нас записан с id=9:

SELECT SYS_CONNECT_BY_PATH(title, '/') as Path
FROM test_table
WHERE id=9
START WITH pid is null
CONNECT BY PRIOR id = pid;


PATH
----------------------------------------------------
/Россия/Воронеж/ООО "Рога и копыта"/Офис 2/Сервер 1


Еще может быть полезен псевдостолбец CONNECT_BY_ISLEAF. Его можно использовать так же, как LEVEL. В этом псевдостолбце напротив каждой строки проставляется 0 или 1. Если есть потомки – проставится 0. Если потомков нет, такой узел в дереве называется “листом”, тогда и значение в поле CONNECT_BY_ISLEAF будет равно 1.

Устали? Осталось немного, самое страшное уже позади. Раньше мы использовали оператор PRIOR, который ссылался к родительской записи. Помимо него есть другой унарный оператор CONNECT_BY_ROOT, который ссылается (ни за что не догадаетесь!) на корневую запись, т.е. на самую первую в выборке.

SELECT id, pid, title, level,
 CONNECT_BY_ISLEAF as IsLeaf,
 PRIOR title as Parent,
 CONNECT_BY_ROOT title as Root
FROM test_table
START WITH pid is null
CONNECT BY PRIOR id = pid
ORDER SIBLINGS BY title;


ID PID TITLE                LEVEL LEAF PARENT               ROOT
-- --- -------------------- ----- ---- -------------------- ------
1      Россия               1     0    Россия
2  1   Воронеж              2     0    Россия               Россия
3  2   ООО "Рога и копыта"  3     0    Воронеж              Россия
6  3   Главный офис         4     1    ООО "Рога и копыта"  Россия
7  3   Офис 1               4     1    ООО "Рога и копыта"  Россия
8  3   Офис 2               4     0    ООО "Рога и копыта"  Россия
9  8   Сервер 1             5     1    Офис 2               Россия
5  1   Лиски                2     0    Россия               Россия
10 5   ЛискиПресс           3     1    Лиски                Россия
4  1   Москва               2     1    Россия               Россия


Стоит отметить, что если в результате выполнения запроса обнаружится петля, Oracle выдаст ошибку. К счастью, ее можно обойти, хотя если в данных содержатся петли – это явно ошибка, в деревьях не бывает петель. На картинке с “бусами” запроса был нарисован оператор NOCYCLE после CONNECT BY – его мы и будем применять. Теперь запрос не будет вылетать. А чтобы определить “больной” участок, воспользуемся псевдостолбцом CONNECT_BY_ISCYCLE – в нем во всех хороших строках будет записано 0, а в тех, которые приводят к петлям, волшебным образом окажется 1.

Чтобы проиллюстрировать это, придется немного подпортить данные. ЛискиПресс ссылается у нас на город Лиски; изменим запись Лиски, чтобы она ссылалась на ЛискиПресс (не забудьте про commit – я вечно забываю):

update test_table set pid=10 where id=5;


Если мы запустим какой-нибудь из предыдущих запросов, увидим, что и Лиски, и ЛискиПресс выпали из выборки, будто их нет совсем. Бегая в цикле, Оракл просто перестал на них натыкаться, т.к. нет пути от записи Россия к городу Лиски. Изменим условия START WITH, чтобы начинать с города Лиски – появится ошибка. Умный Оракл видит что запись уже выбиралась ранее и отказывается бегать в бесконечном цикле. Исправляем ошибку:

SELECT CONNECT_BY_ISCYCLE as cycl, id, pid, title
FROM test_table
START WITH id=5
CONNECT BY NOCYCLE PRIOR id = pid;


CYCL         ID        PID TITLE
---- ---------- ---------- ----------
   0          5         10 Лиски
   1         10          5 ЛискиПресс


Практические примеры



Иерархические запросы можно применять не только там, где есть явная иерархия.

Например, рассмотрим задачу получения списка пропущенных номеров из последовательности. Это бывает нужно, когда в некоей таблице id генерируется автоматически путем увеличения на 1, но часть записей были удалены. Нужно получить список удаленных номеров. По хорошей традиции, это следует сделать одним селектом.

Подготовим тестовые данные. Удалим из нашей таблицы пару записей:

DELETE FROM test_table WHERE id IN (3, 5);


С чего начнем? Во-первых, неплохо было бы получить список номеров подряд от 1 до максимального значения в нашей таблице, чтобы было с чем сравнивать. Выяснить максимальное значение id из таблицы, думаю, не составит никаких трудностей:

SELECT max(id) FROM test_table


А вот чтобы сгенерировать последовательность от 1 до max как раз и понадобится рекурсивный запрос. Ведь как здорово просто взять и получить нужное количество строк! Достаточно будет их пронумеровать – и вот список готов.

SELECT rownum as rn FROM dual
 CONNECT BY level <= (SELECT max(id) FROM test_table);


Конструкция “SELECT … FROM dual” используется, когда надо вычислить значение функции, не производя при этом выборки данных. Dual – это системная таблица, состоящая из одного столбца и одной строки. Запрос из нее всегда возвращает одну строку со значением ‘X’. Благодаря такой умопомрачительной стабильности, эту таблицу удобно использовать в качестве источника строк.

Обычно таблицу, которую нагло используют для получения нужного количества строк, не выбирая сами данные, называют pivot. В качестве такой таблицы может выступать любая большая таблица, в том числе системная. Но использование dual в Oracle является более разумным решением.

Теперь, когда список номеров подряд уже есть, достаточно пройтись по нему и сравнить, есть ли такой номер в проверяемой таблице:

SELECT sq.rn
FROM (SELECT rownum as rn FROM dual
 CONNECT BY level <= (SELECT max(id) FROM test_table)) sq
WHERE sq.rn not in (SELECT id FROM test_table)
ORDER BY rn;


  RN
----
   3
   5


Всё. Ведро начищено до блеска, лошадь вооружена биноклем для остроты зрения. Да не коснется вас ROLLBACK. COMMIT!
maovrn @maovrn
карма
78,6
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

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

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

  • +2
    Весьма познавательно.

    Когда-то, когда появилась mysql5 с рудиментарными хранимыми процедурами, писал такую процедуру для неё, чтоб рекурсивно дерево извлекала. Но это всё равно очень криво работало :(
    • +4
      Не обижайтесь maovrn… дальше поймете почему.
      Для бухгалтерии скорости не надо, а для WEB это жизнь…
      Поэтому.
      Рекурсия это зло (я даже очень категоричен в этом). Теряем конроль над запросами — т.е. уже зло, плюс при хорошей нагрузке на сервер он ляжет и никакие добавления серверов не помогут, потому что нет гибкости… мы не сможим «по человечески» распараллелить сервера…

      Существуют «иерархические» алгоритмы для работы с БД (например Nested Sets, вполне неплохой, но тяжелый в понимании и не совсем иерархический), но я бы назвал это псевдоиерархия…
      MySQL — это реляционная модель, но извините уже отставшая от требований на сегодня. Деревья и ветвления с большой глубиной все больше входят в мир web технологий…
      И всё больше и больше я слышу вопрос, а можно ли «приручить» ...SQL-и для работы с иерархическими структурами, и есть ли панацея.
      Отвечу — есть. И не рекурсией, так как при нагрузке она просто «убьет» сервер…

      Выход есть и уже работает. Я сделал иерархическую CMS (сейчас идет beta-тестирование, разрабатывал в общей сложности 2 года, это не клон теперешних, совершенно другая архитектура) без лишних join-ов и без рекурсии.
      Я анализировал все алгоритмы более года, наконец взял всё лучшие из них и можно сказать сделал свой алгоритм. Единственный его недостаток, немного избыточность данных, но это не текст и избыточность минимальна. Зато по скорости (равномерности нагрузки) и гибкости реляционная модель курит в стороне. Причем все это реализовано даже на таком, не подготовленном к иерархии MySQL
      Кстати из-за этого совсем изменилась архитектура CMS! Теперь она стала меньше, гибче и “универсальнее”. Теперь простыми правилами можно сделать как магазин, форум, социальную сеть… т е он явлеятся унифицированныи и универсальным…
      То же и с нагрукой… Такую архитектуру легко распараллелить… зацепил? ;)
      • +8
        А я для теоремы Ферма чудо-доказательство придумал, идёт бета-тестирование.
        • –8
          Извините но совсем не смешно.
          Хотите поучавствовать. Есть требования. Одно из них соглашение о неразглашении.
          А так как вы шутитите — вам скорее всего откажу.
          • –2
            мда, как обычно стадное явление, один минус поставил — за ним потянулись остальные…
            коммент то «не о чем», тем более «сарказм тема». Внутренние разборки, а у нас как обычно… кого бьют? И не разобравшись вместе со всеми забить человека — детство.
            Сделайте вначале что либо, потом саркастически и поговорим. Имхо ответил правильно, потому что если бы человек хотел увидить, он бы написал: а где можно увидить, пощупать…

            И вообще не понятна психология плюсующих… вы плюсуете чувство юмора или поддерживаете сарказм? Если первое, тогда не понятно минусование ответа… значит второе.
            • +2
              а мне просто не нравится салатовый цвет =)
            • +3
              Подтвердите сначала свои слова о «революционной CMS», предоставьте примеры, алгоритмы, доказательства, в конце концов, и тогда вам, может быть, поверят. Уж не обессудьте, но трындеть любой горазд. А громкие, но голословные и ничем не подкрепленные утверждения — это совсем не то, за что хотелось бы поставить плюс.
            • 0
              Скажите пожалуйста, а есть ли возможность поучаствовать в бетта тестировании? Я когда-то пытался сам что то такое как вы говорите реализовать, но не сил не опыта не хватило. Но уж очень интересно посмотреть на ваш прогресс в этой области.
        • 0
          Вы немного опоздали, её окончательно доказали 14 лет назад.
      • 0
        Ценное замечание. Меня вы ничем не зацепили. Все надо применять с умом. Вполне логично что иерархические запросы более требовательны к ресурсам. К тому же они не предполагают работу с графами, которые встречаются не реже деревьев.

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

        Любопытно было бы взглянуть на вашу CMS. Похоже при ее разработке вы применили nested sets? У этого метода есть один минус: если понадобится передвинуть какую-нибудь ветку (скажем, «Сервер 1» из примера перевезти в Лиски), придется проходить по всем дочерним записям. Впрочем, это не имеет значения, если такое поведение не предполагается или бывает крайне редким.
        • –1
          NS там нет, я от него избавился очень давно. И вам советую.
          Я немного намекну… я анализировал алгоритмы почти год…
          Немного подсмотрел у IBM (коммерческие финансовые программы), но взял совсем немного сути.
          Немного взял у NS — но только суть не архитектуру алгоритма.

          Алгоритм совершенствовался полее года.
          • 0
            Ну вы меня вообще заинтриговали. Обещаете рассказать когда исследования подойдут к концу?
            • –2
              Да вы увидите я напишу в «Я пиарюсь»…
              Только судя по комментам участников (не относится к вам и другим трезвомыслящим людя), а надо ли?
              Что-то после инвайтов, как то ряды разработчиков порядели… столько «детей» появилось…

              Детям: вам папа говорил, что минусовать без причины — признак дурачины? Всегда надо приводить аргументы.
              • 0
                Аргументы: на протяжении уже двух дней подряд от вас от вас здесь есть только куча комментов типа: «вы все дети, потому, что меня минусуете, а я сам написал cms, она революционная и использует революционные алгоритмы, но я вам её не покажу, потому, что она ещё не готова и вообще вы ничего в ней не поймёте, потому вы все дети».

                Зато вы, ничего не предложив в замен, критикуете и отвергаете простое и удобное (в разработке), традиционнон решение — для работы с деревьями использовать рекурсию. Решение, кстати, которому лет больше, чем вам.

                Простите, (уважаемый), вы — пустозвон.
                • 0
                  То что вы «додумываете» себе — это ваше личное горе… я такого не говорил и не имел ввиду. Я пытался переубедить это заблуждение…
                  Показал топик другим специалистам — долго смеялись.

                  Далее…
                  Оо, вы уже перешли на личные оскорбления… :))
                  Так опускаться нельзя молодой человек…

                  Мда, мало вас папа в детстве ремнем бил наверно… ошибки в воспитании видимо, жаль в таком возрасте вы их уже не исправите.

                  Далее отвечаю…

                  Да плюньте вы на мой алгоритм, если он вам не нравится и вы его не видели (а уже обсуждаете).
                  Рекурсия в высокоскоростный БД, это это традиционное заблуждение. Да(!) существуют, другие алгоритмы, в конце концов… да тот же Nested Sets в 1000 раз лучше… или «материализованный путь», а есть и обьединенные эти два алгоритма…
                  Они тоже — универсальные. И вся выборка выполняется одним запросом! Уперлись вы в «свою» рекурсию…

                  Нравиться — ради бога… пользуйтесь, не хотите слушать других… ходите по кругу…
              • 0
                А статейку уже можно посмотреть где-то?
                Интересно бы было сейчас почитать
        • –3
          Вы часто перемещаете ветки?
          Для бухгалтерии это не часто, а для web-а так и вообще раз в полгода максимум.
          Переименование ветки — гараздо чаще, но если грамотно построена архитектура то это тоже очень простой вопрос.
      • 0
        Кстати, помимо реляционных СУБД, рассмотренных мною, бывают еще и иерархические, специально заточенные под хранение иерархических данных. Мне никогда не приходилось с ними сталкиваться (если не считать реестр MS Windows), но мне кажется, раз уж предъявляются жесткие требования к производительности именно на иерархических данных, к ним стоит присмотреться.
        • 0
          Да ну? А как же файловые системы, LDAP (в частности, Microsoft AD), DNS? :)
          • 0
            Не понятно… почему Вам минус поставили… а, я понял, вы поддержали меня :)
            Так как я высказываюсь довольно резко, у меня много «анти-почитателей»…
            Но я всегда высказываюсь резко в только в том случае, если это по пройденному опыту, и я знаю о чем говорю.

            А поставили «просто так», а ведь Вы правы ;)

            Кстати для разработки иерархической БД очень много сути можно взять из файловых систем… (я взял, и доступ и расширения и еще много чего)
            Просто те кто минусовали, врядли вообще что-то сделали… из разряда ламеров.
            Сейчас ламеры опять заминусуют :) Ну, ну… мне от этого не хуже :))

            • 0
              Думаю уже не заминусуют: основной поток читателей уже прошел, напоминание что появился новый комментарий видят только я и merlin_rterm.

              Я только имел ввиду именно иерархическую БД, а не файловую систему, реестр или DNS. То что они по своей сути похожи — это понятно.
              • 0
                Я всегда воспринимал ФС (достаточно продвинутую, не как FAT) именно как иерархическую БД. Под определние ИБД, она, по крайней мере, подпадает.

                DNS — не подпадает, потому, что там нет возможности «перечисления» всех записей.
        • 0
          Сейчас вас удивлю… вы сталкиваетесь каждый день! И почти каждую секунду…
          Вот и ответ: FAT и другие файловые системы :)))
      • –1
        На каком основании вы делаете вывод относительно скорости рекурсивных запросов?
        Вы сами сравнивали производительность или видели какое-то исследование?
        • 0
          На основе 18-летнего опыта в этой области.
          Если вам не важна скорость и вам плевать на контроль запросов… пользуйтесь. Я вам не даю?
          Это самый «легкий» способ, для начинающих.
          Если вы хотите высокопроизводительное web приложение с высокой нагрузкой… я советую забыть про рекурсию.
          О рекурсии уже давно изжевано и написано много статей.
          А вам тяжело самому найти исследования? Их очень много. И все специалисты в один голос пишут, что это зло.
      • 0
        Повелся я на ваш троллинг по поводу добра и зла. Зря вы так категоричны про рекурсию, контроль можно потерять и без рекурсии, банально написав неоптимальный запрос. В дискретной математике рекурсия так же присутствует во многих алгоритмах. Скорее велосипеды — это зло, хотя если хорошенько поискать можно и добрые велосипеды найти.
  • +4
    Автор, отличная статья, послал вам личное письмо по поводу включения статьи в следующий habradigest.

    По поводу создания иерархий хотел бы еще и еще раз разрекламировать hierarchyId MS SQL Server 2008:
    habrahabr.ru/blogs/sql/27774/
    если вы дополните статью небольшим параграфом про hierarchyId, я буду просто счастлив :)
    • +1
      Рад осчастливить хабраюзера. Добавил ссылку.
      Кстати, сам был не в курсе, прочитал с удовольствием.
  • +2
    Очень познавательно. Попробую применить. =)
    • –8
      Если честно, лучше не надо…
      Я описал выше почему.
      • 0
        Эй «минус», а аргументы? как обычно троллим…
      • +2
        опишите ещё, что конкретно применять вместо этого, тогда можно будет отказаться от этого подхода
        • –1
          К сожалению пока свой алгоритм выложить в паблик не могу. (читайте мои комменты «почему»)
          Но могу сказать одно, даже NS и материализованный путь на порядок лучше алгоритма описанного автором.
          • +2
            Я уверен, что стандартные решения, предложенные производителями СУБД и описанные в данном топике, подойдут для большого круга задач. А стандартизованность и простота решения окупит себя по сравнению с «самопальными» алгоритмами, пусть даже и несколько более производительными. Конечно, если дерево станет гигантским и производительность упрется именно в иерархические запросы, возможно, придется что-нибудь переписать. Но я бы тогда начал с переосмысливания хранимых данных и попытался бы уложить их в реляционную модель. Или хотя бы ограничил область выборки. Или использовал бы агрегаты. Следует смотреть по обстоятельствам. Использование нестандартных методов, с моей точки зрения, еще большее зло чем падение производительности при рекурсии.

            Если все будут говорить «все придумали до нас», не будет никакого прогресса. Я искренне желаю вам успехов с вашим алгоритмом. Но в настоящее время ваш алгоритм использовать нельзя, у NS есть свои минусы. Поэтому я не был бы столь категоричен.
            • 0
              Вы шутите?
              Конечно, Вам не предложат коммерческих алгоритмов… это алгоритм для… не хочу матом ругаться, тех у кого денег нет чтобы купить Oracle-вские программы и для того чтобы те кто пользуются этими «алгоритмами», «тормозили» безбожно и бежали в магазин и покупали Oracle-вские программы…
              А название «самопальные» можно под 99% и-нета причесать… заканчиваем холивар. Рекурсия в БД — ЗЛО и не надо других вводить в заблуждение.
              • 0
                Рекурсия в БД — ЗЛО и не надо других вводить в заблуждение.


                Полностью согласен. Проблемы с пониманием этого возникают у программистов, мыслящих только в процедурном ключе. Так же те не понимают как в реляционном мире SQL можно жить без for-ов, while-ов, switch-ей и if-ов… =))
                • +1
                  Кстати, у Оракла в конструкции SELECT есть функции, работающие аналогично switch-ам (DECODE)и if-ам (IIF). Иногда их приходится применять. И не сказал бы что это плохо. Если есть инструмент, почему бы им не пользоваться. Конечно, во всем должна быть мера. Но и подходить к СУБД с позиции тупой хранилки данных, пользуясь только синтаксисом самого первого стандарта SQL-89, согласитесь, тоже не правильно.
                  • +1
                    Пардон, первым был SQL-82. Но суть предыдущего от этого не меняется.
                  • 0
                    Соглашусь =) Но…

                    Но и подходить к СУБД с позиции тупой хранилки данных, пользуясь только синтаксисом самого первого стандарта SQL-89, согласитесь, тоже не правильно.


                    Как раз-таки из-за того, что большинство программистов подходят к СУБД с позиции «тупой хранилки данных» — и приходится прибегать к нестандартным запросам. И вот здесь — инстументы оракла сильно вас выручают =)
                    • +1
                      СУБД — это именно хранилка данных, с интерфейсом для их занесения, перечисления и извлечения.
                      • 0
                        Вы не поняли меня. Я говорил про то, что не стоит "подходить к СУБД с позиции тупой хранилки данных(черному ящику)", т. к. этот подход в большинстве случаев приводит к печальным последствиям(за исключением проектов уровня hello world).

                        Даже самая «навороченная» СУБД не спасёт вас, если ваши ваши таблицы используются в качестве «свалки данных». Защиты от дурака в СУБД — нет =) Учитесь ею правильно пользоваться.
                        • +1
                          Ну, СУБД разные бывают. Те, интерфейс которых построен на языке SQL, как раз и надлежит рассматривать как чёрный ящик. Собственно, SQL для того и придуман, чтобы при запросе указывать только свойства нужных данных, не задумываясь о том, как именно эти данные будут найдены и аггрегированы.
                          • +1
                            Ну, СУБД разные бывают. Те, интерфейс которых построен на языке SQL, как раз и надлежит рассматривать как чёрный ящик.

                            Конечно, в идеале оно так и должно быть. Но в реальном мире вашим «черным ящиком» нужно ещё как-то управлять(устанавливать, настраивать, бэкапить, оптимизировать, масшабировать и т.д. — куча ньюансов) И вот здесь ваши теоретические познания SQL вам уже никак не помогут.
                            • +1
                              Полностью поддерживаю. Изначально SQL предполагался как язык конечного пользователя. Но сейчас он настолько сложен, что нужен программист. Помимо этого, все СУБД имеют в своем арсенале какие-то свои уникальные функции, методы работы и т.д.

                              Например, как ограничить выборку первыми N строками? Такой запрос, особенно в web, выполняется очень часто. А решается он у всех по разному: в mySQL это LIMIT(N), в PostgesSQL это LIMIT N, в Oracle rownum<=N
          • –3
            А я вечный двигатель изобрел только показать не могу пока — тайна:)
            Вам не кажется, что это глуповато?
            • –3
              Не сравнивайте х… с пальцем.

              CMS и вечный двигатель. Ваш сарказм не уместен.
              Я почти некогда не минусую. Но извините… Ваш сарказм — глупость и детство. (в стиле — «сам дурак»)
  • +3
    Можно ещё упомянуть nested sets. Да, вникать в них надо довольно долго, но в итоге результаты на, мой взгляд, себя оправдывают. По крайней мере начинаешь видеть задачу хранения иерархий в несколько другом свете. Способ подходит для всех реляционных СУБД. Показывает своё преимущество при больших уровнях вложенности.
    • +2
      «в создании левой и правой границы для каждого узла» — если я не ошибаюсь это и есть nested sets. не смотрел что в ссылке дал автор.
    • +1
      В методе Селко как раз и используется nested sets. Но спасибо вам за ссылку, у вас этот метод описан более наглядно.
  • 0
    Для небольших деревьев я использую несколько иной подход — написал класс, который формирует дерево в памяти, загружая поля ID, PARENT_ID, TITLE обычным селектом. Для большинства задач этого вполне хватает и гибкость такого подхода оправдывает некоторый расточительный расход памяти.
  • +1
    В MySQL вышел из ситуации тем, что записываю полный путь элемента до корневого элемента (parents_ids=«1,3,5») т.е. уровень можно посчитать по запятым, а ветки выбираю при помощи FIND_IN_SET. Ничего нового в этом нет, но пока удачных реализаций этого метода не находил, хотябы потому что везде где видел подобную реализацию используется LIKE, а мой пока еще не оформлен должным образом чтобы вывести на паблик.
    • 0
      Надо попробовать, пока тоже использую LIKE.
      • –1
        Если вы используете LIKE как %search% — то уж лучше NS ;)

        LIKE можно использовать но как строгое "="
        • +1
          Если его использовать как "=", то почему бы не написать "=", а не LIKE?
    • 0
      Есть проблема с хранением полного пути вместо его генерации на лету — когда надо передвинуть узел на новое место иерархии, то придется пересчитывать и менять все потомки. А при хранении только ссылки на родителя и генерации пути на лету надо изменить только одну запись, что конечно более надежно и более эффективно. Особенно если деревья большие.
      • 0
        Полностью с Вами согласен, перенос веток действительно становиться проблематичной задачей в таком подходе, пока не было задач по переносу веток, а поразмышлять на досуге, времени особо нет.
      • 0
        Это легко делается если у вас есть id узла который меняете и есть новый алгоритм… :)
        Да кстати, а вы часто перемещаете узлы? ;) Я думая, что нет… :)
        Поэтому выполнить одну ресурсоемкую задачу раз в полгода, это не рекурсия которая такую нагрузку дает ежесекундно…

  • 0
    Я думаю, не лишним будет упомянуть, что оператор «with» так же есть в Oracle. И по большому счету никто не запрещает создать иерархический запрос на его основе. Хотя это из серии «а оно надо?». Все же «with» в Oracle удобно использовать для других целей, а не только построения иерархий.
    • 0
      Оператор with в Oracle используется. В частности в конструкции START WITH. Можно с его помощью создать представление. Но вот обратиться к нему в процессе создания этого представления, как в синтаксисе SQL-1999 у меня не получилось (может руки не от туда ростут :-( ). Не могли бы вы написать правильный запрос? Кстати, я сейчас проверял на Oracle 10.
      • 0
        Я говорила про конструкцию типа:
        with
        rec1 as ( select * from dual),
        rec2 as ( select * from dual)
        select *
        from rec1, rec2;

        Наверное, не совсем так выразилась. Я имела в виду, что в оракле есть похожая конструкция «with» использующихся для немного других целей.
        И что она очень похожа на:
        WITH [recursive] имя_алиаса_запроса [ (список столбцов) ]
        AS (запрос)
        основной запрос
  • +8
    Что-бы тут написать такое, чтобы сказать что прочитал с удовольствием, и не схлопотать минус?
  • 0
    «Чтобы понять рекурсию, сначала надо понять рекурсию». — завис.
    • 0
      А почему человеку влепили минус?
      Вы не вдумались, а он почти прав… когда разработчик теряет конроль над запросами — то жди «даун»
      • –1
        Мне собственно без разницы на этот минус, я просто удивлён тому, что я единственный кто находит в этой фразе тавтологию… вероятно минусующие часто говорят что-то вроде:
        Чтобы налить молоко, нужно налить молоко! или нет лучше даже так — «Чтобы правильно минусовать, нужно правильно минусовать!»
        • +3
          По-моему, «тавтология» в данном случае — намеренно добавленная фигура речи, как бы «демонстрирующая» рекурсию. Т.е. это не ошибка.
          • 0
            спасибо :)
        • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Nested Sets, не требует рекурсии, правда все очень интересно запутано, но если один раз распутатся и написать клас обертку, то потом можно не заморачиватся. Вот отличная статейка с примерами www.getinfo.ru/article610.html
    • +2
      Удаление элемента из netsted set очень ресурсоемкая операция.
      • 0
        Согласен, но вобщем все зависит от задачи, например в моей задаче то иерархический список только дополняется обьектами, ну и выборка само собой. Но зато плюс в том что не нужна никакая рекурсия, и это мне определенно нравится.
        • 0
          Хотя… может и мнение мое субьективное, всетаки еще смотря от количества элементов… тоесть при одном-десяти элэментах, разницы в скорости, что например это долго, я не видел. Возможно при большем количестве обьектов буду видеть разницу скорости. Но повторю что сама структура хранения и операции над ней мне нравятся, хоть и не доходил до пиковых каких-то пределов.
        • 0
          Рекурсия — это зло.
          Когда разработчик теряет контроль над запросами (а в рекурсии так оно есть) — жди «дауна»
          • 0
            За то что рекурсия это зло, я согласен, поэтому ее не использую =) Ну в крайнем случае если есть обходной вариант =) Поэтому и использую NS =)
            • 0
              Слава богу от NS я избавился и ничуть не сожалею. Наоборот.
              Пользуюсь совсем другим алгоритмом.
              • 0
                Я за Вас очень рад, но в паблике более достойного я не нашел чем НС, а изучать эту проблему времни небыло, был бы ваш алгоритм в паблике, про который можно почитать, может быть и воспользовался бы им =) А так достойной альтернативы не нашел.
                • –1
                  Согласен, пока не доделаю коробку для CMS в паблик сами понимаете не положу :\
                  Но бета тестрование проходит. Но только на соглашении о неразглашении, и еще кучей требований…
      • +1
        И еще забыли добавить… если вдруг сбой (потеря например записи)… при NS нарушается целостность структуры…
        NS это скорее псеводоиерархия. Какае-то «плоская иерархия» :)
        А вообще, про все это я написал выше
        • 0
          Да и распараллелить (если нагрузка) NS невозможно «по человечески»…
        • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Я вот недавно реализовал дерево так:

    выбрал все данные из базы в одномерный масив обьектов, где сделал индек равный ID
    затем делаю один проход в цикле и если PID не равен нулю делаю такую штуку:

    $pages[PID]->child = &$pages[ID];

    Интересует мнение имеет ли такое решение право на жизнь?
    • 0
      Проблема выбрать значение только одной какой нибудь ветки.
    • 0
      Такое решение имеет право на жизнь, при сравнительно небольшом количестве элементов, но пример вашего кода так будет выглядеть правильнее: $pages[PID]->child[] = &$pages[ID];
      А в противном случае у каждого узла может быть _только_ по одному варианту…
      • 0
        Простите очепятался…
    • –3
      Тоже ресурсоемкий… есть подход гараздо легче.
  • 0
    Ну вот, теперь нам, ораклоидам, все завидывать будут! :)
  • 0
    Спасибо, очень интересно.
  • –1
    Рекурсия порой печально, но иногда приходится.
    Можно пойти немного по-другому способу:

    id (varchar) | title (varchar)
    aa | Россия
    aaaa | Москва
    aaab | Санкт-Петербург
    aaabaa | Павловск
    aaabab | Торфяное
    aaac | Владивосток

    aaza | Мухосранск
    ab | Англия
    ac | Китай

    Как выбрать всю ветку из России?

    Пишу по-русски, т.к. MySQL давно не использовал

    ВЫБРАТЬ ВСЁ, ЧТО В ИДЕНТИФИКАТОРЕ НАЧИНАЕТСЯ С 'aa'.

    Как выбрать всю ветку из России, не включая Россию?

    ВЫБРАТЬ ВСЁ, ЧТО В ИДЕНТИФИКАТОРЕ НАЧИНАЕТСЯ С 'aa' И STRLEN(id) > STRLEN('aa')

    Ну и т.д. Вдруг кому пригодится.
    • +1
      а теперь передвиньте Санкт-Петербург в Китай! Придется менять рекурсивно все потомки! вместо одно только Питера
      • 0
        UPDATE table SET id = CONCAT( [id-китая], SUBSTR( id, STRLEN([id-России]) ) WHERE SUBSTR(id, 0, STRLEN([id-России]) = [id-России]

        Один запрос
        • 0
          не о количестве запросов же речь, а о количестве редактируемых записей
          • 0
            Перенос ветки — не часто выполняемая операция. Обработать пару миллионов записей один раз в месяц можно.
            • 0
              ну я не был бы столь категоричен.
              соглашусь, что в большинстве случаев применения деревьев, модификация не частый случай
              но например в разных оптимизационных задачах это может быть рутинной операцией исполняемой тысячи и миллионы раз
              • +3
                Проблема программистов в том, что для них есть только 3 числа: 0, 1 и бесконечность. Т.е., числа 350 нет. Программист не может осознать тот факт, что как не старайся, но в данном случае не будет больше 350 элементов. Если элементов больше одного, то надо сделать так, чтобы работало и 2 элемента и 2 миллиона элементов. Хотя ведь их ну никак не будет больше 350. Это не в обиду, это одно из наблюдений проектировщиков интерфейсов. Я лишь цитирую. Число 350 взято с потолка, также может быть и 14.

                Разные оптимизационные задачи составляют не такой уж и большой процент от общего числа задач. Да, я не настаиваю на том, что этот подход суперотличен. Я им сам уже давно не пользуюсь. Но для интернет-магазина с рубрикатором до 100 веток его вполне достаточно.

                А сейчас я использую ltree в PostgreSQL. Вполне себе неплохо. Принцип немного похож. На нем работает dmoz.org, так что с производительностью там тоже неплохо.
                • +1
                  :-) Нет в жизни счастья для всех, оно есть только для каждого в отдельности
                  И в каждом случае придется идти на какой-нибудь компромисс
        • 0
          Ребята если вы такой запрос покажите в нормальной фирме… с вами и разговаривать не будут…
          извините конечно… но подставлять тут же высчитываемые данные при помощи CONCAT SUBSTR знаете что сделает? Подумайте сами.
          Я дам подсказку: index
          • 0
            Я это написал для того, чтобы показать, что это можно сделать одним запросом. Не ставя задачу, сделать это быстро и сверхкачественно. К тому же MySQL-ем уже давно не пользуюсь, поэтому и данный способ не использую. Ну и в дополнение, как я уже писал выше: для дерева из 100 веток этот запрос не смертелен. Для 1000 тоже. А для бесконечности — часто ли такие задачи возникают?
            • 0
              Одним запросом? union фактически еще подключение запроса, плюс ко всему рекурсия… это совсем не «один» запрос.

              На вторую часть вопроса отвечу…
              для бухгалтерии не смертельно, они ждут отчетов и по полчаса…
              для web-а — 1 секунад это уже вечность…
              По маркетинговым исследованиям, если юзер не увидел страницу в течении 5-х секунд, 80% (для 3-х — 60%) — что он её закроет и больше не зайдет… для Web-a это равносильно гибели проекта.
              • 0
                Этсамое. Не понял, где вы увидели UNION?

                Что касается 5 секунд, вопрос мне стоял про перемещение одной большой ветки в другую. Обычно это делает администратор раз в полгода, ну уж никак не пользователь по несколько раз в минуту.

                Или мы на разные темы говорим?
            • 0
              Ой сорри я немного перепутал…
              1-ю часть ответа это автору статьи :)
              Но вторая часть ответа подходит и под первую…
              Вы проверяли как у вас в таких запросах используются индексы?
    • 0
      Тут проблема: а если буквы алфавита кончатся?
      • 0
        Все деревья конечны. Не бывает бесконечных деревьев. Если планируется делать ну очень огромный список, можно составные части ключей делать не из двух символов, а из 5 или 10.
        Сколько вариантов может дать звено из 10 англоязычных символов? Если я правильно помню математику, то либо 10^26 либо 26^10. Нормально получается.
        На самом деле и 5 хватит: 5^26 = 1490116119384765625 вариантов соседей одной ветки.
        • 0
          Уж математику-то я напомню: 10 символов, каждый имеет 26 разных значений — 26^10 вариантов (проверочное слово: 8 символов, 2 различных значения — 2^8 = 256 вариантов).

          Неудобно всё равно получается со строкой. Хотя в типичных проектах (скажем, тот же хабр) действительно такая строка в целом не разрастётся больше, скажем, 20-ти символов. Комментарии более 10 уровней нечасто попадаются :)
  • 0
    С рекурсиями в запросах давно разобрался для MS SQL и Oracle, но всё равно почитал с удовольствием, спасибо!
  • +1
    Интересно почитать про реализацию в PostgreSQL
  • 0
    Рекурсия — весьма себе ресурсоемкий процесс. Кроме того требующий от разработчика наличия определенной фантазии. А иногда вообще ставит в тупик и ощущения безысходности и опустошения =))
    (опечатался по Фрейду — написал безысКОДности — успел исправить)

    Поэтому я больше ими не пользуюсь. Один умный парень придумал Nested Sets — и это очень sexy.
    www.dbmsmag.com/9603d06.html
    threebit.net/tutorials/nestedset/tutorial1.html
    а вот по-русски
    www.getinfo.ru/article610.html
    • +1
      Смотрю, про Нестид Сетс уже упомянали здесь.
      В любом случае, эта тема достойна отдельного поста.
  • НЛО прилетело и опубликовало эту надпись здесь
    • –2
      NS тоже не выход, существует лучше алгоритм :)
      здесь :)
      NS это плоская псевдоиерархия, которая тяжело распараллеливается, у которой целостность слабая… да и еще много недостатков.
    • 0
      вставляет, конечно, подольше.
      где-то начиная с тысячного узла в середку дерева аккурат по минуте на узел (дерево многоуровневое и ветвистое).
      это уже (sorry for my english), не вставляет ни фига.
      а вообще самая большая проблема с деревьями — не выбора ветки от единого родителя (эта вещь оптимально делается не рекурсией, а скорее циклом — поличество запросов равно уровню вложенности, посему в самом худшем случае (дерево у нас — лиана или виноград какой-то, и каждая ветка имеет ровно одного потомка) эта штука будет работать с той же скоростью, что рекурсия, в лучшем же — намного быстрее) а правильной сортировки выбранного. И тут возможны варианты (помимо nested sets — потому как с обновлениями и вставками на нем все просто совсем ахово получается).
      • –2
        Ага это NS — узнаю :)
        Знаете, есть алгоритмы быстрее, вот что я скажу… я выше писал уже о них.
        NS — плоский псевдоиерархический алгоритм, с кучей недостатков. Вот просто в паблике пока ничего нет лучше… а в коммерческих проектах — есть :)
        • +1
          ну, мы тоже используем свои алгоритмы. Правда, разрабатываем их чуть подольше. В целом сейчас оно уже работает вполне удволетворительно (кусок дерева — чтобы использовались индексы — вложенностью 10, объемом где-то в 30000 узлов отрабатывается примерно за 1 — 2 секунды, а с закешированным запросом — раз в 100 быстрее). Правда, наше решение катит только под PostgreSQL (возможно будет работать и под ораклом, если оно шагнуло вперед после 2001 года).
          А под мускуль существует альтернатива на dklab — изящный и очень быстрый запрос, правда, с ограничением по вложенности — не более 32 уровней (или 31).
          • 0
            Я тестировал на уровнях вложенности ~20 (больше у меня почему-то не получается придумать для Web задачи :)
            и 100`000 записях (сколько узлов не считал), главная страница… Ctrl-P:
            Всего 32: 0.025
            Всего &php: 0.241

            На сколько я помню на dklab всё что связано с иерархией затихло… тот алгоритм что у них есть, назвать тяжело алгоритмом.
            Он очень сырой… люди там встретили трудности (а трудности там были немалые, да еще и с кучей join) и… забросили всё это дело подальше :) Это было кажется года 2-3 назад… dbtree кажись называлась.

            :) Могу теперь с оглядкой на 3 года назад только улыбнуться :)
            • +1
              Гы. Я использую, правда для вложенности не более 3-х.
              И только для вычисления агрегатной таблицы.
              Преимущество этого способа вижу только в том, что он обладает атомарностью — во время выполнения никакая зараза не сможет модифицировать MyISAM таблицу.
              Минус у способа один и очень существенный — размер SQL запроса сильно увеличивается с уровнем вложенности.
              Но этот монстроидальный запрос работает довольно шустро.
              • 0
                Размер увеличивается join-ами?
                • 0
                  join`ы — это сущие пустяки. Проблема в вычислении нужных полей — приходится много условий проверять, чтобы определить какого уровня текущая запись. Если подскажете как оптимизировать, с удовольствием перейму опыт :)
                  Запрос такой (алгоритм тщательно не разрабатывался и не скрывается от общественности):

                  UPDATE catalog_tree, (
                  SELECT t0.cid,
                  CASE WHEN t0.pid=0 THEN t0.shown
                  WHEN t1.pid=0 AND t0.shown>0 THEN t1.shown
                  WHEN t2.pid=0 AND t0.shown>0 AND t1.shown>0 THEN t2.shown
                  ELSE 0 END AS shown,

                  CASE WHEN t0.pid=0 THEN 0
                  WHEN t1.pid=0 THEN 1
                  ELSE 2 END AS level,

                  CASE WHEN t0.pid=0 THEN t0.cid
                  WHEN t1.pid=0 THEN t1.cid
                  WHEN t2.pid=0 THEN t2.cid
                  ELSE 0 END AS id0,

                  CASE WHEN t0.pid=0 THEN t0.title
                  WHEN t1.pid=0 THEN t1.title
                  WHEN t2.pid=0 THEN t2.title
                  ELSE 0 END AS title0,

                  CASE WHEN t0.pid=0 THEN 0
                  WHEN t1.pid=0 THEN t0.cid
                  WHEN t2.pid=0 THEN t1.cid
                  ELSE 0 END AS id1,

                  CASE WHEN t0.pid=0 THEN ''
                  WHEN t1.pid=0 THEN t0.title
                  WHEN t2.pid=0 THEN t1.title
                  ELSE 0 END AS title1,

                  CASE WHEN t0.pid=0 THEN 0
                  WHEN t1.pid=0 THEN 0
                  WHEN t2.pid=0 THEN t0.cid
                  ELSE 0 END AS id2,

                  CASE WHEN t0.pid=0 THEN ''
                  WHEN t1.pid=0 THEN ''
                  WHEN t2.pid=0 THEN t0.title
                  ELSE 0 END AS title2,

                  CASE WHEN t0.pid=0 THEN CONCAT(LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0'),'000000000000000000000000')
                  WHEN t1.pid=0 THEN CONCAT(LPAD(HEX(t1.sort),4,'0'),LPAD(HEX(t1.cid),8,'0'),
                  LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0'),'000000000000')
                  WHEN t2.pid=0 THEN CONCAT(LPAD(HEX(t2.sort),4,'0'),LPAD(HEX(t2.cid),8,'0'),
                  LPAD(HEX(t1.sort),4,'0'),LPAD(HEX(t1.cid),8,'0'),
                  LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0')) END AS srt
                  FROM
                  catalog_tree t0
                  LEFT JOIN catalog_tree t1 ON (t0.pid=t1.cid)
                  LEFT JOIN catalog_tree t2 ON (t1.pid=t2.cid)
                  ) AS v_catalog_tree
                  SET catalog_tree.shown=v_catalog_tree.shown,
                  catalog_tree.level=v_catalog_tree.level,
                  catalog_tree.id0=v_catalog_tree.id0,
                  catalog_tree.title0=v_catalog_tree.title0,
                  catalog_tree.id1=v_catalog_tree.id1,
                  catalog_tree.title1=v_catalog_tree.title1,
                  catalog_tree.id3=v_catalog_tree.id3,
                  catalog_tree.title3=v_catalog_tree.title3,
                  catalog_tree.srt=v_catalog_tree.srt
                  WHERE catalog_tree.cid=v_catalog_tree.cid
                  • 0
                    Небольшое пояснение. Дерево построено по простейшей схеме родитель-ребенок.
                    Введены вычислимые поля сортировки и пути к корню для ускорения выборок и осуществления обратной совместимости со старой версией каталога, которая дерево держала в 3-х таблицах.

                    PS: Уже можно насчитать 5 способов хранения дерева в таблице:
                    1) id-parent_id
                    2) NS
                    3) Path to root
                    4) Разбиение каждого уровня по отдельным таблицам
                    5) X — загадочный очень производительный способ, но не известный общественности :)
                    • 0
                      Могу посоветовать как делает IBM в своих коммерческих программах…
                      Они хранят id-шники ветки

                      id | id1 | id2 | id3…

                      где если ничего нет то 0, всей ветки т.е. последний id ветки будет свой же id

                      тогда очень легко делать и выборку и обновление… если знаешь id узла спокойно апдейтишь
                      в стиле UPDATE… WHERE id3 (например) = 12345

                      и в таком же духе…

                      А выборку тоже очень легко делать

                      SELECT

                      WHERE
                      id2 =2

                      // и ограничиваем по ветке
                      id5=0

                      Немного избыточно, но очень быстро и очень гибко.
  • 0
    Пора бы уже mysql добавить возможность работы с рекурсивными запросами.
    • 0
      Если грамотно подойти — его можно приручить, причем с 4-й версии (даже с 3-й) :)
      • 0
        Я имел ввиду с иерархическими…
        Если вы хотите скорость и выдерживать большие нагрузки…
        Запомните, рекурсия в архитектуре БД — ЗЛО
  • 0
    Эмм, по поводу MySQL…

    set @a = '444'; # root id
    select *, @a := concat_ws(',', @a, ID) from TreeItems where parentID IN (@a);

    Разве не подходит? Или я что-то упустил?
    • 0
      а индексы ;)
      • 0
        А что не так с индексами? Я и правда что-то упустил?
  • +1
    Небольшие поправки. Вот это:

    SELECT rownum as rn FROM dual
     CONNECT BY level <= (SELECT max(id) FROM test_table);
    


    Работает только в 10g, в версиях ниже выдается ORA-01473: cannot have subqueries in CONNECT BY clause.

    А вот такое, почему-то, в 9-ке выдает всего одну строку вместо 10 (почему — не знаю):

    SELECT 1, level FROM dual
     CONNECT BY rownum <=10
    


    • 0
      Хм, интересно. У меня как раз 10g и оба запроса работают как надо. Если найду решение для 9-ки, дам знать.
      • 0
        Вот здесь: www.sqlsnippets.com/en/topic-11821.html в разделе «Gotchas» и подразделе «Issues» как-то мутно объясняют, что, де, это из-за того, что CONNECT BY обязан содержать PRIOR, и приводят рабочий вариант для девятки:

        select *
        from   (select level from dual connect by level < 10) ;
        


        • 0
          Да, именно так. На sql.ru обсуждалась такая бага 9-ки.
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Спасибо большое за статью! Честно говоря, раньше не слышал об иерархии в базах. Думаю, что не я один :)
    Если бы делал показ дерева на сайте, поступил бы так же, как Вы описали — загрузка верхнего уровня, затем подзапрос по клику на узел.
    Добавляю статью в избранное.
    P.S. Исправьте, пожалуйста «ни раз» -> «не раз».
  • +1
    И всё бы хорошо, да только полный граф этими запросами в Оракле не получишь.
  • +3
    Народ, честно, не могу понять практического применения описанных запросов, с точки зрения конечного продукта, а не академических или консольных задач. Сколько работал с иерархическими данными нигде на уровне базы и SQL-запросов не нужно было выбирать все дерево, а если и нужно было, то обычного selectа и orderа хватало. А задачи были от навороченных отчетов, до достроения OLAP-системы на реляционной Sybase 9 в банке. Может приведет кто-то конкретный пример применения?
    • 0
      Что-то никто не спешит отвечать, буду сам отдуваться. Я никогда не слышал о крупных проектах, использющих иерархические данные способом, описанным в статье. Возможно такие есть, но, скорее всего, нет. Применимость иерархических запросов можно выделить в большую группу мелких и средних проектов.
      Для них это приемлемо потому что:
      1. Структура данных становится простой и понятной.
      2. Код не загроможден лишними функциями обработки строк для построения дерева средствами внешнего для SQL языка.
      3. Гораздо быстрее написать несколько команд иерархического запроса, чем городить огород.
      4. Используются стандартные методы. Программисту, который будет заниматься поддержкой и развитием, будет проще разобраться.
      А минус всего один: относительно низкая производительность.
      Пока плюсы перекрывают минус, почему бы не использовать. Я лично применял несколько раз, когда требовалось отобразить дерево.

      Или товарищей чисто от самого факта «более низкая производительность» коробит? Так давайте все на си писать, никаких php, ruby и т.д. — они же медленнее.
      • 0
        ничего себе, промазал как-то комментом…
        см. ниже :)
      • –1
        Данным способом существуют только масса мелких проектов…
        Для больших и сильнонагруженных используются в основном другие алгоритмы.

        Я вообще не понимаю. Очень многие разработчики используют БД как хранилище данных и полностью забывают про архитектуру.

        Для тех, кто использует БД как хранилище данных и предназначена рекурсия… это как отмычка. Для всех замков: долго — но может откроет… В коммерческих проектах — так делать нельзя. Надо подходить сначала к БД -как к архитектуре.
        • 0
          В коммерческих проеках оценивается не производительность сама по себе, или качество кода само по себе, а стоимость решения. Если мне дешевле написать рекурсивный запрос и купить в два раза больше ОЗУ и процессоров, я так и сделаю.

          Процессоры дешевле программистов.
          • 0
            Нахватались умных слов? :)
            Распараллельте потом на серверы «рекурсию»…
            Я на вас посмотрю…
            А грамтоная архитектура БД + «не рекурсия» — свободно… вы сами противоречите себе…
            Слышал звон — не заню где он
      • 0
        Спасибо за ответ. Позвольте прокомментировать Ваши ответы.

        1. Структура данных от запроса не зависит.
        2. Согласен
        3. Если для консоли, то да, а если на туже HTML-страницу вывести со всеми стилями и прочим? Ведь весь огород городится для презентационности представления.
        4. Спорный вопрос, я бы не сказал, что подобные запросы настолько изящны, что в них легко разбираться.

        А вот вопрос производитеьности к получению данных имеет самое прямое отношение. Честно говоря, жалко людей, у которых на генерацию всяких отчетов уходит очень много времени.
        • 0
          Тогда и прокомментирую.

          1. Это скорее относилось к структуре данных по отношению к методу NS: нумерация строк и ссылки на родителей гораздо понятнее левых и правых сторон.
          3. При выводе на веб-страницу, достаточно обворачивать каждую строку (вернее поля строки) в HTML-теги в порядке поступления строк без всякой дополнительной обработки.
          4. Дело вкуса, не буду спорить.

          Я не думаю что отчет должен содержать миллионы строк. Зачем это человеку? А выборка из сотни-другой строк происходит настолько быстро, что человек не в состоянии заметить разницы, какой вид запроса применял программист.
  • 0
    Разрешите контр-аргументы.
    1) Для простых и понятных структур данных статьи пишут совсем другого характера.
    2) Язык SQL не предназначен для решения подобного рода задач, поэтому решение получается чрезвычайно кривым и сильно зависимым от конкретного производителя RDBMS. Согласен, что функции построения дерева нужно инкапсулировать в какой-то изолированый модуль, но при грамотной архитектуре, это не большая проблема.
    3) Гораздо быстрее реализовать и затем легче поддерживать древовидные структуры с помощью паттерна Composite на уровне более развитого языка программирования, и не городить огород.
    4) Используются не стандартные методы, как уже упомянулось в п. 2. Рабозбраться с этой хренотенью будет реально тяжело. Программист должен быть experienced в конкретной базе данных.

    Про performance и scalability говорить не будем.
    • +2
      Зерно истины есть в ваших словах. Не буду спорить. Мне вот только непонятно, что это за гипотетический программист такой, котороый может разобраться с Composite или другим модулем для построения дерева, но при этом не в состоянии осилить несколько команд sql-запроса. И еще по поводу пункта 4: очень желательно чтобы программист был осведомлен о возможностях СУБД, с которой он работает. Потому что в каждой есть свои нюансы. В одной надо делать так, в другой иначе, в третьей можно и так, и эдак. Нельзя весь функционал базы данных сводить к кроссплатформенному SELECT * FROM…, и потом дообробатывать внешними средствами.
    • 0
      sql хоть и не прдназначен для иерархических данных, но при грамотном подходе научить можно.
      • 0
        у Вас пластинка заела?
        расскажите же, наконец, о своем мега-методе!
  • +1
    Добавлю в копилку автора, запрос на выборку всех потомков для заданного родителя, для СУБД MaxDB.

    declare c cursor for with recursive tree (node_id, node_pid, node_level) as
    ( select id, pid, 0
    from test_table where Условие_выборки_родительского_элемента
    union all
    select id, pid, node_level+1
    from test_table, tree
    where tree.node_id = test_table.pid
    )
    select node_id
    from tree
    order by node_level
  • +2
    Мои 5 копеек по поводу репрессий в отношении рекурсий: ну ёлки-палки, ну кто ж будет такой глупый, чтобы реально делать рекурсивный запрос каждый раз? Собрал один раз структуру в хэш (массив), сериализовал (если надо), сунул в кеш, да перестраиваешь время от времени, когда структура в базе изменяется. При чем не обязательно перестраивать всю структуру целиком, достаточно просто участками, т.к. перестраивать довольно часто надо отнюдь не всё, только определенные ветки.
    Даже с учетом ресурсоёмкости процесса перестраивания кеша (что происходит, наверное, не часто) всё это всёравно выглядит лучше, чем materialized path, да и ведет себя не так «забавно» как NS.
    Как-то так.
    • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Вот что значит использовать для отображения дерева таблицы.
    В Cache всё было бы значительно проще:

    пусть данные хранятся в глобале ^Tree

    Распечатаем глобал и посмотри что внутри:
    zw ^Tree

    ^Tree(«Россия»)=1
    ^Tree(«Россия»,«Воронеж»)=2
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"")=3
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Главный офис»)=6
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 1»)=7
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»)=8
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»,«Сервер 1»)=9
    ^Tree(«Россия»,«Лиски»)=5
    ^Tree(«Россия»,«Лиски»,«ЛискиПресс»)=10
    ^Tree(«Россия»,«Москва»)=4

    Уже это дерево легко преобразовать в xml и отобразить в интерфейсе.

    Предположим что этого не достаточно и нам необходимо самим рекурсивно оббегать структуру — будем использовать низкоуровневую функцию $query ($q)

    результатом выполнения комманды:
    s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) w l,! }

    будет:
    ^Tree(«Россия»)
    ^Tree(«Россия»,«Воронеж»)
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"")
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Главный офис»)
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 1»)
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»)
    ^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»,«Сервер 1»)
    ^Tree(«Россия»,«Лиски»)
    ^Tree(«Россия»,«Лиски»,«ЛискиПресс»)
    ^Tree(«Россия»,«Москва»)

    Добавим отступы (пусть никого не пугает вложенный цикл
    f i=1:1:len {w " "} ) и идентефикаторы выполним комманду:

    s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) f i=1:1:len {w " "} w "(",$g(@l),") ",$qs(l,len),! }

    получим:
     (1) Россия
      (2) Воронеж
       (3) ООО "Рога и копыта"
        (6) Главный офис
        (7) Офис 1
        (8) Офис 2
         (9) Сервер 1
      (5) Лиски
       (10) ЛискиПресс
      (4) Москва
    


    Всё. Никаких хитростей никаких наворотов стандартные низкоуровневые функции. Стандартное дерево, в котором и хранятся все данные. Даже индексы не задействованы.
    • 0
      про скорость обработки таких деревьев я скромно умолчу — время рекурсивной обработки зависит от размера дерева логарифмически. То есть вывод по скорости дерева с миллионом узлов аналогичен select * From table (предположим что имеем там миллион записей). Насчёт сортировки тоже заморачиваться не стоит.

      И вообще преобразовать табличные данные в деревянные — легко, обратная процедура не всегда возможна и очень ресурсоёмка (имеется ввиду на уровне БД а не интрефейса).
    • 0
      Строчка запроса взрывает мне мозг, уж больно синтаксис непривычный. Но выглядит очень впечатляюще. В Oracle, как ни крути, деревья всего лишь дополнительная фича, а не главная составляющая.
      • +1
        тогда распишу сокращения понятнее будет
        set l="^Tree" //устанавливаем значение переменной
        
        for { //цикл
         set l=$query(@l) //берём следующий по очереди элемент дерева (алгоритм  обхода функции $query сверху вниз затем справа налево)
        
         quit:l="" //выходим из цикла когда всё обошли
         set len=$querylength(l) //определяем глубину вложенности (вниз) текущего узла
        
         for i=1:1:len {write " "} //печатаем отступы 
        
         write "(",$get(@l),") ",$querysubscript(l,len),! //печатем в скобках значение узла + его имя 
        }
        

        сокращённый вариант
        s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) f i=1:1:len {w " "} w "(",$g(@l),")",$qs(l,len),! }
        
        • 0
          ошибка сверху — вниз затем слева — направо
        • 0
          Так значительно понятнее! Спасибо. Вполне себе алгоритмический язык. Пожалуй, такой запрос написать даже проще, чем в Oracle.
          • 0
            это не «запрос» — это язык mumps. Прелесть Cache в том, что они соединили язык программирования и данные, с которыми он работает, в одной посудине. Так что этот код — аналог php+sql, где вместо запросов к базе юзаются $f() функции.
  • 0
    Спасибо Вам большое за познавательную статью! Думаю, что многим из Хабрасообщества эта статья будет реально полезна. Также понравилась форма преподнесения: просто о сложном, подробно, интересно. Говорю, как человек, только изучающий язык запросов.
  • +1
    возможно уже кто-то комментировал…
    пример запроса с использованием WITH — «зациклен»

    вероятно, подразумевалось вот так:
    WITH RECURSIVE
     Rec (id, pid, title)
     AS (
       SELECT id, pid, title FROM test_table
       UNION ALL
       SELECT test_table.id, test_table.pid, test_table.title
        FROM Rec, test_table
        WHERE Rec.id = test_table.pid
       )
     SELECT * FROM Rec 
     WHERE pid is null;
    
    • 0
      Я не эксперт в MS SQL, ошибка возможна. Но я в упор не вижу чем различается ваш запрос от приведенного в статье.
      p.s. Приятно, что материал пользуется спросом и комментируется спустя 7 лет после публикации :-)
      • +1
        выбор полей в рекурсивной части CTE должен быть из таблицы, а не из CTE, иначе «зацикленность».

        извиняюсь: в прошлом комментарии забыл перенести еще условие выборки корневого уровня в CTE, иначе запрос только корневую строчку вернет.
        плюс выражение recursive в ms sql, да и в oracle лишнее.

        в общем, как-то так:
        WITH
         Rec (id, pid, title)
         AS (
        -- корневая часть
           SELECT id, pid, title FROM test_table
             WHERE pid is null
           UNION ALL
        -- рекурсивная часть
           SELECT test_table.id, test_table.pid, test_table.title
            FROM Rec, test_table
            WHERE Rec.id = test_table.pid
           )
         SELECT * FROM Rec;
        


        статья обрела здесь некую фундаментальность за эти 7 лет в вопросах рекурсии средствами SQL.
        спасибо )
        • 0
          Спасибо, выглядит разумно, хоть и не могу проверить на практике. Запрос в статье поправить сейчас сложно — придется все листинги кода переписывать с новым форматированием хабра (иначе html-теги видны). Надеюсь читателям, пришедшим из поисковика, хватит терпения добраться до последних комментариев.

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