В тридесятый раз про деревья. Выращиваем.

[iSlayter]

В тридесятый раз про деревья. Выращиваем.

Вообщем. Не знаю что выбрать: Adjacency List || Nested Sets.

Где будут использоваться?

Каталог, вложенность 3х уровневая. Но может перерасти в нечто большее. Изменяться будет редко. Но перенос дочерних узлов между ветками будет довольно частым (почему и не спрашивайте, таково ТЗ).

Что выбрать?

Есть ли у кого-либо свои библиотеки для работы с деревьями по этим двум алгоритмам, которыми вы можете поделиться?
DBTree не подходит, т.к. тащит за собой ADOdb. По Adjacency list вообще ничего готового не видел но понравилась идея с указателями (в теоретическом форуме).

Про деревья почитал в мане mysql'я. Полдня работы минимум уйдёт на реализацию Nested Sets своего. Ну и не особо просто алгоритм.

С Adjacency list всё проще. Дерево кешироваться не будет (нагрузки не те). С построением дерева будет сложнее (т.е. кода чуть больше)... не простож отсортировать по left, как во вложенных множествах.

Т.е. даже вопрос в другом наверное.

Кому приходилось строить деревья и в каких ситуациях? Какой способ хранения вы выбрали? Почему?

 

[jonjonson]

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

 

[melo]

Adjacency List - пользуюсь этим.

почитать можно тут - http://phpwiki.ru/Tree/Al

 

[Wicked]

iSlayter
у nested sets есть пара минусов:
- большинство изменений затрагивают в среднем половину всех элементов, из которого следует, что оно ведет себя плохо при частых модификациях дерева, а особенно при модификации больших деревьев.
- в нем используется более тонкая денормализация, что требует более тонкой же работы с ней.

 

[Popoff]

http://phpclub.ru/faq/Tree/Faq?v=lzx#FaqSelect

 

[iSlayter]

А какой наиболее оптимальный способ в AL получить всех детей?

Джойнить таблицу саму на себя Н раз? Там вроде ограничения есть 30-32 джойна, да?

Или это не оптимальный вариант?

 

[Фанат]

друже, у тебя вложенность 3 уровня. при чем здесь 30?

 

[iSlayter]

Фан*т, просто интересуюсь об ограничениях. Хватит за глаза, безусловно. Вопрос в другом, таблицу на себя джойнить -- оптимальный вариант? Запросы шустренько проходят.
или лучше так http://phpclub.ru/talk/showthread.php?s=&threadid=98248 ?

 

[WP]

Popoff
У Вас там баг.

    if(empty($a_tree[$f['k_parent']]))
      $a_tree[$f['k_parent']]=array();

empty() возвращает истину для пустого массива, поэтому ветка инициализируется дважды. Нужно заменить на !isset.

$a = array();
echo empty($a);
// 1

 

[StUV]

для редактирования можно использовать обычные id -> parent_id
для селектов - то представление (view), которое наиболее подходит для вашей задачи (перегенерять по событию, периодически, ...)

ессно "зависит от..." - в первую очередь от объема данных, но... вам виднее что/как в частностях