Иерархические модели данных: список смежности и вложенные множества

Question

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

Вопрос в том, какой тип иерархической модели данных больше подходит для такой ситуации. Проект основан на фреймворке Django, и его особенности (admin i-face, обработка моделей ...) должны быть рассмотрены.

Большое спасибо!

Answer 1

Согласно этим статьям:

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), для которой модель вложенных множеств демонстрирует достойную производительность и может рассматриваться как хранимая иерархическая информация.»

Answer 2

Я бы использовал модифицированный алгоритм обхода дерева предзаказов, MPTT, для такого рода иерархических данных. Это обеспечивает отличную производительность при обходе дерева и поиске детей, если вы не возражаете против небольшого штрафа за изменения в структуре.

К счастью, у Django есть отличная библиотека для этого, django-mptt . Я использовал это в ряде проектов с большим успехом. Также есть django-treebeard , который предлагает несколько альтернативных алгоритмов, но я им не пользовался (и в любом случае он не так популярен, как mptt).

Answer 3

Nested sets лучше для производительности, если вам не нужны частые обновления или иерархическое упорядочение.

Если вам нужны обновления дерева или иерархическое упорядочение, лучше использовать parent-child модель данных.

Он легко создается в Oracle и SQL Server 2005+, и не так легко (но все же возможно) в MySQL.

Answer 4

http://www.sqlsummit.com/AdjacencyList.htm

Answer 5

Список смежности гораздо проще поддерживать, а вложенные множества гораздо быстрее запрашивать.

Проблема всегда заключалась в том, что преобразование списка смежности во вложенные множества заняло много времени благодаря очень неприятному методу «push stack», который загружается с RBAR. Таким образом, люди заканчивают тем, что занимаются действительно сложным обслуживанием во вложенных наборах или не используют их.

Теперь вы можете съесть свой торт и съесть его тоже! Вы можете выполнить преобразование на 100 000 узлов менее чем за 4 секунды и на миллион строк менее чем за минуту! Все в T-SQL, кстати! Пожалуйста, смотрите следующие статьи.

Иерархии на стероидах # 1: преобразование списка смежности во вложенные наборы

Иерархии на стероидах # 2: замена для расчетов по вложенным множествам