Вывод дерева

[cyberix]

Тему поднимаю не первый раз и не только здесь
Ситуация такая - есть база с категориями продуктов. Для того чтобы смотрелось решил вывод сделать не сплошным, а в виде дерева. Получил результат который меня удовлетворил только при помощи рекурсии. Это собственно преамбула
Амбула - как только категорий стало порядка 250 сразу стало понятно что нужно сделать что-то другое. Пока вижу наилучшим решением такой вывод - сначала на панели навигации выводим самый верхний уровень категорий. потом открываем необходимую ветку уровнем ниже. и так далее. параметры передавать скорее всего через адрес. кто может поделиться алгоритмом/тыкнуть в фак/привести пример/поделиться рабочим примером/дать идею к реализации?

 

[venetu]

Не знаю где ты поднимал эту тему, на самом деле на твои грабли человечество наступало уже миллионы раз, и выход конечно же есть.
Тебе дорога сюда:

Для просмотра ссылки Войди или Зарегистрируйся

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

И да, в википедии про это тоже есть.

 

[cyberix]

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

 

[venetu]

а если мне прийдет в голову перетащить дочернюю категорию под другого родителя при достаточно большом количестве категорий? как я понимаю этот метод хранит структуру дерева уже в базе, не проще ли ее формировать на лету?

Сколько раз в минуту тебе приходит в голову идея перетащить дочернюю категорию под другого родителя? Не торопись отвечать сразу, подумай. Оцени это число, от .. и до ..

Теперь второй вопрос. Сколько раз в минуту тебе приходится "формировать структуру дерева на лету"? Над этим вопросом ломать голову не стоит, достаточно заглянуть в логи.

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

Вот как-то так..

 

[cyberix]

дурак, согласен не подумал
просто хотелось бы проще, но с вложенными множествами будет проще и по факту быстрее при большом кол-ве категорий
изначально мне не хотелось (из соображений банальной лени) менять структуру базы:
cat_id, cat_name, cat_description, cat_parent, cat_activity - ну это в принципе банально, ничего военного нет
буду мучаться - с этим методом работаю впервые, как получится сделать рабочий модуль - выложу исходники с камментами

 

[medvoodoo]

Решение по формированию меню в случае когда таблица со связями один ко многим(для каждого элемента указан родительский элемент)
1)Забирается вся база с сортировкой по pid в массив(если надо кешируется)
2)Построение делается проходами(по уровням), соотв кол-во проходов == кол-ву уровней вложенности.
3) на базе результата строится уже дерево.
Реализации не выложу, т.к. они завязаны на кучу библиотек, плюс у меня все это делается через кеш xml, а дальше домом я спокойно выдираю нужный кусок из кеша.
----------------------------------------------------------------------------
второй вариант при необходимой рекурсии:
0)передача исходных данных в метод
1)Запрос
2)Формирование запроса для уровня N+1 (IN(id1,...)), где сумируются все id из результатов/параллельно запись в меню узлов N уровня
3)Если IN() не пустой Вызов метода (1)
в итоге опять же кол-во запросов == вложенность+1 проверено на ~3 000 записей

 

[cyberix]

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

Начнем с вопроса, - а нужен ли вообще Nested Set? Чтобы ответить на этот вопрос, достаточно упомянуть, что если мы хотим вывести все поддерево в 1000 позиций, хранящегося методом Adjacency List - то мы должны 1000 раз обратиться к базе данных. Не радужные перспективы.

Тем не менее, "высокий порог вхождения" в Nested Sets, сложность системы управления деревом, и высокая вероятность разрушения целостности дерева при отсутствии транзакций, - все это не сделало Nested Sets чрезмерно распространенным.

 

[venetu]

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

Обход массива из 250 элементов хоть циклами, хоть рекурсией - это ж тоже происходит за мгновения.

Я не понимаю, откуда тормоза? Ты не хочешь выгребать все двести, а вместо этого делаешь селекты только нужных? Ну окей, делай тогда снизу вверх - сначала самый вложенный уровень, потом его родителя и "братьев родителя", потом их общего родителя и его братьев, и так пока до корня не доберешься. Будет у тебя 5 селектов (или сколько там у тебя уровень вложенности максимальный). Вряд ли больше. Это хуже, конечно, но тоже не смертельно. Очень быстро делается.

Или передавай категорию в виде строки, типа там "1-23-47-141". И селект тогда тоже будет один - "WHERE parent IN (0,1,23,47,141)". Там потом подсуетить немного с выводом, но опять же - все операции в памяти, на небольшом массиве - откуда тормоза?

 

[cyberix]

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