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

первая колонка это id
вторая cid
третья имена категорий
cid это индекс той категории которая является категорией на уровень выше данной

вот скрипт который должен выводить все категории и под категории в виде дерева

проблема в том что если в какойто категории несколько подкатегорий то $o все равно наращивается на 1 и следующая подкатегория смещается хотя должна находиться на том же уровне.. помогите поправить этот баг..   

p.s. вот так сейчас скрипт выводит дерево:


Это сообщение отредактировал(а) lancelot555 - 7.11.2006, 03:17

lancelot555, так не подойдет?


кажется, первый вариант был с ошибкой - присмотрелся, исправил...

Это сообщение отредактировал(а) SelenIT - 7.11.2006, 22:22

Вот тут самая толковая (ИМХО) из всех статей, посвященных алгоритмике управления Nested Sets
Проще один раз сделать правильный класс для деревьев и пользоваться им, чем нагружать базу и скрипт рекурсивными (или циклическими) переборами.

Eugene_Bond, осмелюсь не согласиться, все зависит от задачи. У nested sets свои ограничения, у списков смежности - свои, и в каждом конкретном случае нужно смотреть баланс плюсов и минусов (например, делать перемещение ветви в nested sets в старых версиях mysql, где нет хранимок и транзакций, как-то страшновато). А вот тут Дмитрий Котеров убедительно демонстрирует, что даже многократный self-join в списках смежности (которым так любят пугать новичков) не так уж и страшен...

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

Alone, а какая избыточность в выводе в случае Adjacency List?

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

а панацеи не бывает. 
nested sets, как я понимаю, в текущей форме применима только для хранения дерева, но не графа. В отношении каталога это может выглядеть, как, например, попытка отнести цифровые фотоаппараты и в "Фото", и в "Оргтехнику" одновременно. 
надо бы в "Религиозные войны"   

skyboy,  Совершенно верно.
Тут уж как говорится кесарю - кесарево, слесарю - слесарево.


SelenIT,  Я имел ввиду тот тестовый кусок, который представлен по ссылке
Меня смутило кол-во возвращаемых столбцов и повторяющееся имя ветки.


Гм... А Вы уверены в своих словах? Какая избыточность может наблюдаться при отображении разделов корня + подразделов заданного, если он возвращает _ИМЕННО_ разделы первого уровня + подразделы заданного, и ничего лишнего...

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

Alone, я имел в виду избыточность не при выводе, а при хранении. Насколько мне известно, даже поле level, используемое в большинстве реализаций nested sets - это уже не часть исходной модели, а ее расширение (избыточность ради удобства).

По ссылке, согласен, выводится немало лишнего - но это ж только демонстрационный пример. Можно ограничить избыточность вывода одними id-ами, а сами данные выбрать, к примеру, еще одним join-ом по условию. А в простейшем выводе всего дерева одним запросом с последующей элементарной (пусть даже рекурсивной) перестановкой ветвей, по-моему, избыточности нет...

skyboy, насчет "религиозных войн" полностью согласен, тема действительно интересная) Мое мнение, даже если ограничиться рассмотрением только деревев (графы пока за кадром): adjacency list хранит именно структуру дерева (связей), а поскольку на практике нужно работать с каким-то представлением этой структуры, для его получения нужны дополнительные действия, зато представление в итоге может быть любым. Nested sets же хранит только одно из возможных представлений дерева (типа проекции структуры на плоскость), и пока потребности ограничиваются этим представлением - все ОК (лучше не бывает), как только выходят за его рамки - так всё...

Предлагаю AJAX'ом строить. Кликаешь по ноде, получаешь ее ID, посылаешь запрос на сервер, там идет поиск наследования и возвращается набор дочерних нод.

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


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



Избыточность часто бывает не только вредна, но и полезна


Это уж точно удобнее чем циклом генерировать еще один JOIN для среза определенной глубины :-)


Ну, а резюмируя: сам использую как одно представление, так и другое. Иногда микс -- избыточный, но оооочень удобный.

...по-моему, так нередко бывает и с "фанатами" nested sets, до и после встречи с  необходимостью пересортировки нод на каждом уровне  И сказанное ими в первой фазе также не стоит слепо принимать за абсолютную истину.


По-моему, вообще оптимальный вариант, особенно для высокой нагрузки.
Некая аналогия с MVC в пределах базы: "модель" - в списках смежности, "view" - в nested sets ;)

Именно.

Более того, при массовых перетусовках ветвей можно хеш nested tree перестроить "задним числом" как раз по parent id обычного дерева.