У меня есть каталог продуктов. Каждая категория состоит из разного количества (в глубине) подкатегорий. Количество уровней (глубокое) неизвестно, но я совершенно уверен, что он не будет превышать 5,6 уровней. Изменение данных значительно реже, чем чтение.
Вопрос: какой тип иерархической модели данных более подходит для такой ситуации. Проект основан на структуре Django, и следует учитывать его особенности (admin i-face, обработка моделей...).
Большое спасибо!
Nested sets лучше для производительности, если вам не нужны частые обновления или иерархическое упорядочение.
Если вам нужны обновления дерева или иерархическое упорядочение, лучше использовать модель данных parent-child.
Он легко строится в Oracle и SQL Server 2005+ и не так легко (но все же возможно) в MySQL.
Я бы использовал алгоритм обхода дерева с измененным предзаказом, MPTT, для такого рода иерархических данных. Это позволяет добиться высокой производительности при обходе дерева и поиске детей, если вы не возражаете против штрафа за изменения в структуре.
К счастью, у Django есть отличная библиотека, django-mptt. Я использовал это в ряде проектов с большим успехом. Там также django-treebeard, который предлагает несколько альтернативных алгоритмов, но я не использовал его (и он не кажется таким же популярным, как mptt в любом случае).
В соответствии с этими статьями:
http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/ http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/
"MySQL - единственная система из четырех (MySQL, Oracle, SQL Server, PostgreSQL), для которой модель вложенных множеств демонстрирует достойную производительность и может считаться сохраненной иерархической информацией".
Список Adjacency намного проще в обслуживании, а вложенные наборы намного быстрее запрашиваются.
Проблема всегда заключалась в том, что преобразование списка Adjacency List в Nested Sets длилось благодаря очень неприятному методу "push stack", который загружался RBAR. Таким образом, люди в конечном итоге выполняют очень трудное обслуживание в Nested Sets или не используют их.
Теперь ты можешь получить свой торт и съесть его! Вы можете сделать преобразование на 100 000 узлов менее 4 секунд и на миллион строк менее чем за минуту! Все в T-SQL, кстати! См. Следующие статьи.
Иерархии на стероидах # 1: Преобразование списка привязок к вложенным наборам
Иерархии на стероидах # 2: Замена вычислений вложенных наборов