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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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 5

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

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

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

Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets

Hierarchies on Steroids #2: A Replacement for Nested Sets Calculations