У меня есть каталог продукции. Каждая категория состоит из разного количества (в глубине) подкатегорий. Количество уровней (глубоких) неизвестно, но я уверен, что оно не будет превышать 5,6 уровней. Изменения данных происходят гораздо реже, чем чтение.
Вопрос в том, какой тип иерархической модели данных больше подходит для такой ситуации. Проект основан на фреймворке Django и его особенности (админка, работа с моделями...) должны быть учтены.
Большое спасибо!
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), для которой модель вложенных множеств показывает достойную производительность и может рассматриваться как хранимая иерархическая информация».
Список смежности намного проще поддерживать, а запросы к вложенным наборам выполняются намного быстрее.
Проблема всегда заключалась в том, что преобразование списка смежности во вложенные наборы занимало слишком много времени из-за действительно неприятного метода «проталкивания стека», который загружается с помощью RBAR. Таким образом, люди в конечном итоге выполняют действительно сложное обслуживание вложенных наборов или не используют их.
Теперь вы можете получить свой торт и съесть его тоже! Вы можете выполнить преобразование на 100 000 узлов менее чем за 4 секунды и на миллион строк менее чем за минуту! Все на T-SQL, между прочим! Пожалуйста, ознакомьтесь со следующими статьями.
Иерархии на стероидах №1: преобразование списка смежности во вложенные наборы
Иерархии на стероидах №2: замена расчетов с вложенными множествами
