Иерархическая структура

[AbS_]

Наверно самое частое применение этой структуры данных встречается в меню. И при первом же шевеление мозга всплывает самое простое решение для схемы в БД это:
id | parent_id | name

А вот дальнейшее шевеление извилин, наталкивает на мысли что, такой подход хотя и кажется логичным и понятным для человека, становит не тривиальные задачи для реализации манипуляций с ним.
Если подходить ближе к реалиям, то предположим у нас есть дерево меню:
|итем.1
-|итем.1.1
-|итем.1.2
--|итем.1.2.1
--|итем.1.2.2
|итем.2
-|итем.2.1
--|итем.2.1.1
--.......-|итем.2.1.1.1.....1
.
.
--......-|итем.2.1.1.{n}...{n}
|итем.3
|итем.4

В общем имеем больше дерево с большим количеством вложений, при нашей структуре БД хранить такое труда не составит, но возникает вопрос, как реализовать поиск всех узлов заданного узла.
Говоря еще проще, как написать SQL запрос, который это реализует?

[samdark]

Если требуется не очень тривиальная работа с деревом вроде «выбрать все ответы на все мои комментарии», лучше посмотреть в сторону Nested Set.

[AbS_]

В общем в ходе длительного гугления было найдено 3и распространенных алгоритма:
1) Adjacency List
2) Materialized Path
3) Nested Set
У каждого из методов есть + и -. Так же, напомню что для Nested Set реализовано расширение для Yii http://www.yiiframework.com/extension/n ... t/#license

У меня стоит задача: Создать модуль управления меню сайта. Заранее не известно об уровне вложенности и прочее.
Выглядит это так: В админке сайта, пользователь может создавать пункты меню, и перемещать их между родительскими узлами, то есть создавать иерархию меню. Понятно что делаться это будет не так уж и часто, да и кол-во записей не будет очень большим.
Вот основываясь на этих требованиях и то что удалось нагуглить про иерархию, я встал перед выбором чего же все таки использовать.
Может все же в данном случае и нет большой ризници в выборе алгоритма, и стоит взять то что уже реализовано для Yii?

[pirrat]

В вашем случае однозначно Nested Set, поскольку вставки и апдейты дерева будут происходить редко(только в админки), а выборки часто(в клиентском разделе).
Указанный extension я использовал в своих проектах, вполне качественное расширение, хотя и пришлось допиливать его..

[samdark]

Вообще их немного больше: http://www.gsbelarus.com/gs/modules.php ... le&sid=314

В этом случае я бы также выбрал NS. Кстати, есть ещё одно расширение для NS в YiiExt.

[AbS_]

Вообще их немного больше: http://www.gsbelarus.com/gs/modules.php ... le&sid=314

В этом случае я бы также выбрал NS. Кстати, есть ещё одно расширение для NS в YiiExt.

Что то, поиск http://www.yiiframework.com/search/exte ... Nested+Set выдает всего 3и результата. Или смотреть надо где то еще?
А в http://code.google.com/p/yiiext/ такого не наблюдаю.

[timlar]

Я тоже копал инфу по данному вопросу в свое время. В итоге остановился на Nested Sets. Довольно неплохо в плане работы с деревом. И сортировать удобно, и выбирать только конечные узлы, выбирать потомков от определенного родителя, перемещать, создавать вложенные узлы и т.д. Работает все довольно шустро

Здесь живой пример: http://shop.yii.pp.ua/

[AbS_]

Было бы совсем круто, если бы кто то приспособил http://www.jstree.com/
для таких целей)

[timlar]

Я думал прикрутить, но потом отпало желание использовать такую кучу js ради такого мизерного функционала.

[samdark]

http://code.google.com/p/yiiext/source/ ... odel/trees