Вывод дерева

Тема в разделе "Как сделать...", создана пользователем cyberix, 19 янв 2009.

Статус темы:
Закрыта.
  1. cyberix

    cyberix

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

    venetu

    Регистр.:
    28 мар 2007
    Сообщения:
    735
    Симпатии:
    261
    Не знаю где ты поднимал эту тему, на самом деле на твои грабли человечество наступало уже миллионы раз, и выход конечно же есть.
    Тебе дорога сюда:

    http://tigor.com.ua/blog/2008/12/02/introduction-in-nested-sets/

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

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

    cyberix

    Регистр.:
    29 дек 2006
    Сообщения:
    170
    Симпатии:
    42
    вложенные множества это конечно да, но...
    переиндексирование смещений занимает порядочно времени. а если мне прийдет в голову перетащить дочернюю категорию под другого родителя при достаточно большом количестве категорий? как я понимаю этот метод хранит структуру дерева уже в базе, не проще ли ее формировать на лету?
     
  4. venetu

    venetu

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

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

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

    Вот как-то так..
     
  5. cyberix

    cyberix

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

    medvoodoo Постоялец

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

    cyberix

    Регистр.:
    29 дек 2006
    Сообщения:
    170
    Симпатии:
    42
    буду ковырять все-таки в сторону оскоммерса - исходники есть, там именно то что нужно, только разобраться что и откуда
    рекурсией-то и не хотелось бы - кол-во запросов возрастет.
    по вложенным множествам кроме удобства конечной работы и скорости выборки положительного тож пока не вижу
     
  8. venetu

    venetu

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

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

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

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

    cyberix

    Регистр.:
    29 дек 2006
    Сообщения:
    170
    Симпатии:
    42
    я и не говрил что тормоза - хочется чтобы было оптимально ) я изначально подкрутил под себя пример функции - валяется в инете, достаточно распорстраненная, она выводит сразу раскрытое дерево, что не есть гуд.
    в оскоммерсе так и сделано - передается через урлу, сейчас разбираю алгоритм
     
Статус темы:
Закрыта.