PHP FAQ from PHPclub.ru: Tree/FaqSelect ...

Как выбрать самый подходящий способ хранения деревьев в моем проекте?

popoff

1. Списки смежности (AL)
+: выборка всех непосредственных детей для заданной вершины – очень быстро
-: выборка всех детей для заданной вершины (всего поддерева) – долго
-: выборка всех родителей для заданной вершины (определение пути) – долго
-: определить размер поддерева – долго
-: порядок элементов в уровне не может храниться в структуре дерева
-: проверка, является ли одна вершина дочерней по отношению к другой – долго, если вершины не являются непосредственными родственниками
+: добавление новых элементов в дерево – быстро
-: удаление ветки дерева – долго
+: перемещение веток дерева – быстро
+: количество узлов в дереве – не ограничено
?: устойчивость к ошибкам – средняя (если «исчезает» какой-то элемент, то исчезает только соответствущее поддерево)
+: понимание – легко

2. Вложенные множества (NS)
?: выборка всех непосредственных детей для заданной вершины – выполняется одним запросом, но долго (без использования индексов) в случае, если этой вершине соответствует поддерево значительных размеров.
+: выборка всех детей для заданной вершины (всего поддерева) – быстро
?: выборка всех родителей для заданной вершины (определение пути) – выполняется одним запросом, но часто без использования индексов (долго).
+: определить размер поддерева – очень быстро
+: структура дерева позволяет задавать порядок элементов в уровне
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро
-: добавление новых элементов в дерево – долго
+: удаление ветки дерева – быстро
-: перемещение веток дерева – долго
+: количество узлов в дереве – не ограничено
-: устойчивость к ошибкам – низкая (если «исчезает» какой-то элемент, то все дерево становится неправильным)
?: понимание – разобраться в операциях выборки – просто, в операциях модификации – сложно

3. Вложенные интервалы (NI)
?: выборка всех непосредственных детей для заданной вершины – выполняется одним запросом, но долго (без использования индексов) в случае, если этой вершине соответствует поддерево значительных размеров.
+: выборка всех детей для заданной вершины (всего поддерева) – быстро
?: выборка всех родителей для заданной вершины (определение пути) – выполняется одним запросом, но часто без использования индексов (долго)
?: определить размер поддерева – дольше, чем у вложенных множеств, но быстрее чем у списков смежности
+: структура дерева позволяет задавать порядок элементов в уровне
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро
?: добавление новых элементов в дерево – быстро, если есть свободное место. Если свободного места нет, то дольше, чем у списков смежности, но быстрее, чем у вложенных множеств.
+: удаление ветки дерева – быстро
-: перемещение веток дерева – долго, дольше чем у вложенных множеств. Но если есть достаточное свободное место – быстрее, чем у вложенных множеств.
?: количество узлов в дереве – не ограничено, но при большом количестве остается мало свободного места.
-: устойчивость к ошибкам – низкая (если «исчезает» какой-то элемент, то все дерево становится неправильным)
?: понимание – разобраться в операциях выборки – просто, в операциях модификации – сложно, намного сложнее, чем для вложенных множеств

4. Материализованные пути с использованием строк (MS)
?: выборка всех непосредственных детей для заданной вершины – выполняется одним запросом, но с использованием поиска по длинному строковому индексу (level)
?: выборка всех детей для заданной вершины (всего поддерева) – выполняется одним запросом, но с использованием поиска по длинному строковому индексу (tree)
+: выборка всех родителей для заданной вершины (определение пути) – очень быстро (path)
?: определить размер поддерева – выполняется одним запросом, но с использованием поиска по длинному строковому индексу (stree)
-: порядок элементов в уровне не может храниться в структуре дерева (хотя над этим можно подумать) (order)
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро (parent)
+: добавление новых элементов в дерево – очень быстро (insert)
+: удаление ветки дерева – быстро, но дольше чем у вложенных множеств за счет использования индекса по строковому полю (remove)
?: перемещение веток дерева – быстрее, чем у вложенных множеств, но дольше, чем у списков смежности (move)
+: количество узлов в дереве – не ограничено (size)
+: устойчивость к ошибкам – высокая (если «исчезает» вершина, то дерево остается все равно правильным) (error)
+: понимание – разобраться в операциях выборки – просто, в операциях модификации – относительно просто (unders)

5. Материализованные пути (by Tropashko: рациональные дроби, последовательности Farey, фракталы; сильно обобщено) (MT)
?: выборка всех непосредственных детей для заданной вершины – не ясно (level)
?: выборка всех детей для заданной вершины (всего поддерева) – не ясно (tree)
+: выборка всех родителей для заданной вершины (определение пути) – очень быстро (path)
?: определить размер поддерева – не ясно (stree)
+: структура дерева позволяет задавать порядок элементов в уровне (order)
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро (parent)
?: добавление новых элементов в дерево – не ясно, (insert)
?: удаление ветки дерева – не ясно (remove)
?: перемещение веток дерева – не ясно (move)
-: количество узлов в дереве – очень сильно ограничено (size)
?: устойчивость к ошибкам – не ясно (в общем случае вершины в дереве не зависимы, но алгоритмы, использующие этот способ хранения дерева, могут налагать некоторые ограничения, влияющие на устойчивость к ошибкам) (error)
-: понимание – очень сложно (unders)

Построим таблицу:

su1d
Когда ты хранишь лишь ссылку на родителя, то получить одним запросом весь путь от элемента дерева к вершине не получится. Надо делать рекурсию. Если же у тебя хранится обход дерева, то всё получается легко, просто и, что немаловажно, быстро. Минус второго подхода в том, что при добавлении/удалении записи, надо пересчитывать часть дерева, но на вебе кол-во обращений на чтение дерева намного больше его изменений, так что такое решение видится более удобным.

На чтении и поиске быстрее вложенные множества быстрее, чем Списки смежности и Материализованные пути со строками, на изменении каталога (добавление/удаление/перемещение) неслабо проигрывает Спискам смежности, но на вебе обычно поиск чего-то посетителем производится намного чаще, чем изменение каталога админом, поэтому всё получается как надо.

Я не хочу и не берусь утверждать, что Nested Sets в общем случае лучше, чем Adjacency List. У каждого способа свои плюсы, у каждого свои минусы. Я использую как тот, так и другой, но чаще всего – вложенные множества. Это – лишь моё личное предпочтение, и вовсе не обязательно оно должно стать чьим-то ещё.

Недостаток метода, предложенного Tropashko (Материализованные пути), в том, что слишком быстро кончается integer. В первом предложенном способе знаменатель возрастает со степенью двойки, что позволяет иметь не более 16 (32) уровней вложенности. Второй способ – последовательности Фейри уже получше, и у самого Тропашко даже получилось создать дерево на 1М узлов. Однако, он пошёл дальше и предложил кодировать дерево через преобразования Мёбиуса, что вроде как уже имеет право на жизнь, хотя даже там числа растут как последовательность Фибоначчи, что тоже налагает существенные ограничения на количество узлов в дереве. Воложенные множества ещё самые добрые, поскольку там зависимость возрастает лишь как 2n.

Cамой пригодной, единственно бесконечной моделью «для всего», похоже, так до сих пор и является лишь Adjacency List. Все остальные методы так или иначе накладывают ограничения на максимальное количество узлов в дереве. На малых объёмах данных и Вложенные Множества очень хороши и удобны. Интерес как раз в том, чтобы найти модель, не сильно ограничивающую объёмы, но и предоставляющую более удобный механизм доступа к записям, чем это делается с Adjacency List.

Смотрите так же:
Когда нужно использовать Nested Sets? В чем его достоинства и недостатки?
При при использовании Nested Sets из-за сортировки на уровне все летит в трубу!

demiurg: SQL Trees
http://www.livejournal.com/users/demiurg/53125.html