Категории c неограниченной вложенностью (более 8к)

Обсуждение документации второй версии фреймворка. Переводы Cookbook и авторские рецепты.
Аватара пользователя
ElisDN
Сообщения: 5026
Зарегистрирован: 2012.10.07, 10:24
Контактная информация:

Re: Категории c неограниченной вложенностью (более 8к)

Сообщение ElisDN » 2018.02.13, 20:04

Wizard писал(а):
2018.02.13, 17:59
как на счет https://github.com/paulzi/yii2-materialized-path, доводилесь работать?
Без разницы, какой из алгоритмов:

Nested Sets
Closure Table
Materialized Path

Любой в плане выборок будет удобнее, чем Adjacency List.

Аватара пользователя
SiZE
Сообщения: 2593
Зарегистрирован: 2011.09.21, 12:39
Откуда: Perm
Контактная информация:

Re: Категории c неограниченной вложенностью (более 8к)

Сообщение SiZE » 2018.02.13, 20:37

Wizard писал(а):
2018.02.13, 17:59
как на счет https://github.com/paulzi/yii2-materialized-path, доводилесь работать?
у всего свои плюсы и минусы
Как выбрать самый подходящий способ хранения деревьев в моем проекте?

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)
https://phpclub.ru/faq/Tree/Faq там же сравнительная таблица

Wizard
Сообщения: 157
Зарегистрирован: 2018.02.05, 13:41
Контактная информация:

Re: Категории c неограниченной вложенностью (более 8к)

Сообщение Wizard » 2018.02.13, 22:40

как по мне самый оптимальный вариант Materialized Path, на всякий случай заведу еще parent_id (пока еще не знаю надо ли но пусть будет)

основные плюсы для меня

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

тестирую, минусов на данный момент не нашел даже при работе с 8к категориями

Ответить