Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 51
Вопрос к аудитории: как вы решаете задачу вывода дерева в MySQL? Встроенные процедуры? Внесение избыточности в таблицы?
сортировкой по идентификатору родителя =))
а остальное уже сделает клиент.
а остальное уже сделает клиент.
Библиотеку DBSimple юзаем.
организовываем хранение дерева другими методами, в зависимости от условий ;)
Nested Sets
* можно какую-нить статью об етой технике?
если на базе РНР - буду вдвое рад. если на другом языке - тоже рад. но больше разбиратся будет. главное - по SQL нужно понять как ето нормально делать.
если на базе РНР - буду вдвое рад. если на другом языке - тоже рад. но больше разбиратся будет. главное - по SQL нужно понять как ето нормально делать.
Как раз на базе PHP и MySQL: http://www.getinfo.ru/article610.html
материала достаточно, вот например http://phpclub.ru/faq/Tree?v=w5u
nested sets + немного хранимых процедур по управлению деревом.
рекурсия, имхо плохо, по скрости чтения, ns самый быстрый метод хранение (про вставку узлом промолчим(: )
рекурсия, имхо плохо, по скрости чтения, ns самый быстрый метод хранение (про вставку узлом промолчим(: )
Я храню данные в подобной же таблице (id - идентификатор элемента, id_parent - идентификатор родителя, data - какие нибудь доп. данные элемента дерева). Затем делаю выборку всей таблицы в массив (arrData). По полям id и id_parent функцией рекурсивного обхода выстраиваю ещё один вложенный многомерый массив (т.е. массив масивов, в которых могут быть элементы массивов), который представляет собой структуру дерева (arrStructure). И потом по этим двум массивам, масиву труктуры и массиву данных, делаю вывод. Т.е. обхожу полностью массив структуры определяю положение и расставляю данные.
Наверняка лучше сделать такое хранимой процедурой на сервере СУБД.
Был так же вариант без рекурсии, он быстрее работает чем с рекурсией, но настолько незначительно (проводились тесты с несколькими тысячами записей), что сложность его реализации проигрывает перед легкостью реализации с рекурсией. Поэтому решено было всё таки рекурсией реализовывать построение структуры дерева.
А вот насчёт сортировки по идентификатору родителя, простите, но это бред, так правильной структуры дерева не достичь, т.к. вложенность может быть бесконечно большой.
Наверняка лучше сделать такое хранимой процедурой на сервере СУБД.
Был так же вариант без рекурсии, он быстрее работает чем с рекурсией, но настолько незначительно (проводились тесты с несколькими тысячами записей), что сложность его реализации проигрывает перед легкостью реализации с рекурсией. Поэтому решено было всё таки рекурсией реализовывать построение структуры дерева.
А вот насчёт сортировки по идентификатору родителя, простите, но это бред, так правильной структуры дерева не достичь, т.к. вложенность может быть бесконечно большой.
Юзаю materialized path. Конечно, Nested Sets часто побыстрее работает, но зато matpath удобней, легко ручками править дерево. Особенно удобно, когда в БД храниться структура сайта и применяется mod_rewrite. в этом случае, берем url и простеньким запросом находим нужную нам ветвь (в этом случае в качестве пути применяю латинские имена узлов, а не id)
Могу кинуть create proc, но оно не влазит в коммент.
Подскажите, как сделать - кину...
Подскажите, как сделать - кину...
до этого я думал что знаю mysql
Это MS SQL.
не совсем, дело в том, что приведенный пример парсится с ошибкой
почему это так я написал ниже
почему это так я написал ниже
Это не MS SQL. На самом деле это стандарт SQL 99. Эту конструкцию поддерживают: DB2, Sybase iAnywhere, MS SQL. Не знаю как Oracle, но там точно есть другая конструкция типа:
select ...
from tree_sample
start with id = ....
connect by prior id = id_parent
* This source code was highlighted with Source Code Highlighter.
См. ниже — я уже писал об этом.
Хммм. Честно в описаниях по PL/SQL не встречал такой конструкции, обычно везде приводят «родную» конструкцию вида start with ... connect by ... . В очередной раз убеждаюсь, что оракл всегда бежал впереди паравоза=)
Спецы по PostgreSQL поделитесь, как у вас с этим?
Спецы по PostgreSQL поделитесь, как у вас с этим?
Автору стоит указать, что в MS SQL (даже в 2008) нет ключевого слова recursive, в этой СУБД его следует опускать
Автору спасибо. Теперь подумаю, чтобы вернуться к нормальным деревьям, вместо этих Nested Sets... хотя и к ним уже привык.
Я думаю, что Nested Sets будут побыстрее работать, хотя не сравнивал. Конечно, Nested Sets гораздо сложнее реализуются. Надо будет попробывать провести эксперимент по сравнении скорости для разных способов реализации дерева.
Действительно, nested set при выборке из него будет работать быстрее. Сложности в нем нет по одной причине - его уже столько раз обмусолили и сделали столько реализаций... что думать уже даже ненадо :) При необходимости и в nested set можно столбец parent_id добавить(иногда бывает полезно).
Я был бы рад если бы вы поэкспериментировали с новым типом hierarchyid для MS SQL 2008 и сообщили нам о своих результатах. Этот тип как раз и придуман для реализации иерархий.
В PostgreSQL есть библиотека ltree. Позволяет получать дерево простым селектом и очень быстро. Дерево хранится в своем типе, и не очень удобно в манипуляциях (перенос веток). Для манипуляций писал свои функции, но процесс получения самого дерева или ветки - песня.
можно не использовать ключевое слово recursive - а просто 'with' - создаётся временное представление. Жаль что в MySQL нельзя в таком же духе строить рекурсию. На днях пришлось использовать старый дедовский способ - рекурсию делать на клиенте.
Автору следовало бы указать, что это называется Common Table Expressions (CTE) и, очевидно, ничего общего с рекурсивными запросами в Oracle не имеет. Кроме того, CTE используются не только не только для рекурсии.
P.S.
Возможно, следует перенести топик в блог по SQL.
P.S.
Возможно, следует перенести топик в блог по SQL.
Топик я перенес. У меня просто кармы не было, чтобы туда написать.
Я писал просто про рекурсивные запросы, а не про Common Table Expressions (CTE), поэтому решил, что это лишнее.
Oracle я никогда не использовал и так и не смог найти поддерживает ли он этот синтаксис, поэтому решил просто указать, что это часть стандарта SQL 99 и каждая база, которая полностью поддерживает этот стандарт должна поддерживать и эту конструкцию. Oracle, как я понял, не поддерживает ни эту конструкцию ни SQL 99, а придерживается своих стандартов.
Я писал просто про рекурсивные запросы, а не про Common Table Expressions (CTE), поэтому решил, что это лишнее.
Oracle я никогда не использовал и так и не смог найти поддерживает ли он этот синтаксис, поэтому решил просто указать, что это часть стандарта SQL 99 и каждая база, которая полностью поддерживает этот стандарт должна поддерживать и эту конструкцию. Oracle, как я понял, не поддерживает ни эту конструкцию ни SQL 99, а придерживается своих стандартов.
Стандарт для крупных промышленных разработок - Oracle. Там конструкция "connect by prior" уже давно и работает неплохо. В других случаях и базы, и нагрузки поменьше.
Oracle стандартом не является. Он очень популярен у нас в стране, так как часто его получали бесплатно.
Например, в США DB2 не сильно отстает от Oracle по использованию.
Например, в США DB2 не сильно отстает от Oracle по использованию.
Был у меня случай, когда нужно было построить дерево из однонаправленного графа, т.е. переходы происходят строго в одном направлении, но ветки могут как расходиться, так и сходиться.
На Оракле я решил это хранимой процедурой, которая помещала в локальную таблицу (ту, то из type объявить можно) корневые элементы, проставляла им айдишники и начинала вычитывать для каждой позиции из локальной таблицы её потомков, добавлять их в конец списка и проставлять им парентом айдишник элемента, по которому они вычитывались. До и после вычитки потомков элемента запоминалась количество элементов (локальные счетчики, просто инкрементились при добавлении). Если мы приходили в конец списка и для последнего элемента потомков больше не обнаруживалось — построение дерева останавливалось.
В случае неоднонаправленного графа пришлось бы плясать с проверкой на вхождение добавляемого элемента в список уже существующих, что невероятно затормозило бы алгоритм, но, к счастью, обошлось.
На Оракле я решил это хранимой процедурой, которая помещала в локальную таблицу (ту, то из type объявить можно) корневые элементы, проставляла им айдишники и начинала вычитывать для каждой позиции из локальной таблицы её потомков, добавлять их в конец списка и проставлять им парентом айдишник элемента, по которому они вычитывались. До и после вычитки потомков элемента запоминалась количество элементов (локальные счетчики, просто инкрементились при добавлении). Если мы приходили в конец списка и для последнего элемента потомков больше не обнаруживалось — построение дерева останавливалось.
В случае неоднонаправленного графа пришлось бы плясать с проверкой на вхождение добавляемого элемента в список уже существующих, что невероятно затормозило бы алгоритм, но, к счастью, обошлось.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Рекурсивные SQL запросы