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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

В соответствии с этими статьями:

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 4

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

Answer 5

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

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

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

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

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