Деревья

Смотря для каких целей. Например, для вывода меню в админке (где дерево всегда выводится целиком) я храню в базе серилизованный многомерный массив, который вывожу рекурсией. Для его редактирования в той же админке, "на лету" в нем создаются вспомогательные элементы (id,level,parent_id) и затем они удаляются, перед серилизацией и сохранением в базу с целью уменьшить размер массива и ускорить выдачу.

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

Softex, интересный метод :)

robust, честно говоря, думал, что светлые головы что-нибудь еще выдумали. В целом мысль ясна, однако, после Nested Sets мне трудно придумать, где практичней использовать метод с parent-id (хотя в свой класс заложил и этот ключ :) )

Способы хранения деревьев в базах данных в вики на phpclub.ru - весьма рекомендую.

Сам в основном использую Adjacency List (т.е. сохранение parent id), в основном из-за простоты и стабильности. У Nested Sets основная беда случается, когда вставляешь узел куда-нибудь в середину дерева, т.к. приходится переписывать смещения у всех узлов правее нового узла, а при больших базах это о-о-о-очень долго.

Сейчас пытаюсь (очень аккуратно, и, пока, безрезультатно) комбинировать Adjacency List и Nested Sets. Есть мысли в двух направлениях.

Во-первых, можно на Nested Sets организовать только часто доставаемую иерархию, а прочие объекты присоединять по parent id. Например, если речь идет о магазине, структура разделов (которых редко бывает больше двух сотен) выстраивается на Nested Sets, т.к. ее часто нужно выводить целиком, а товары присоединяются паренту (т.к. чаще всего одним запросом достаются товары определенной категории). Но при этом, например, теряется преимущество Nested Sets на удалении, товары придется удалять в несколько запросов.

Во-вторых, в некоторых случаях бывает нужно работать с достаточно глубокой структурой, которая, при этом, постоянна. Для таких случаев я пытаюсь сделать возможность хранения отдельных ветвей дерева на Nested Sets. Правда, послднее время склоняюсь к тому, что это не очень нужно и не очень выполнимо =)

Кстати говоря, пара замечаний насчет рекурсии при подходе Adjacency List. Во-первых, в рекурсивных запросах нет ничего страшного. Как правило, запросы идут довольно простые запросы, и редко их бывает очень много. Во-вторых, в критических ситуациях проблема решается кешированием (если ваша система поддерживает помодульное кеширование). В-третьих, где-то на форуме Котерова (во, нашел топик, он живет здесь) предлагали довольно оригинальное решение. Суть такая, что для каждого узла можно сохранять уровень вложенности. Тогда, например, чтобы вытащить всех родителей узла, достаточно level раз приджойнить табличку со структурой саму к себе по полу parent. Сам не тестил, но идея занятная.

PS. Справедливости ради, стоит заметить, что есть еще подход Materialized Path. Мне он показался кривым и неэффективным, однако, возмжно натолкнет кого-нибудь на правильные мысли =)

Коля Дубр, спасибо за подробный ответ.

А что по этому поводу у Кнута? У меня опять утырили нужный том с полки. Пойду убивать скоро.

А Oracle позволяет без всяких циклов построить дерево. У него в PL/SQL для этого операторы есть. Довольно интересно и удобно получается...

Пользуюсь Nested Sets, вобщем-то все ок, правда я храню в основном дерево категорий. На вывод все очень просто и удобно, в 1 запросе можно что угодно получить(вроде бы все). На ввод только сложно, я долго и нудно первы раз писал ф-ю добавления так чтобы ничего не забыть :)

А для каких задач нужно часто добавлять, как-то не сталкивался?

Удаление как ни крути а редкая штука, да и то через админку, так что в итоге это не самые важные проблемы, когда выбирал Nested Sets ориентировался в основном на то что вывод очень хорош :)

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

А можно поподробнее, несовсем Вас понял?