Modelos hierárquicos de dados: adjacência Lista vs. aninhadas Sets

Question

Eu tenho um catálogo de produtos. Cada categoria é composta por um número diferente (em profundidade) de subcategorias. O número de níveis (de profundidade) é desconhecida, mas a certeza de que ele não será superior a de 5,6 níveis. As alterações de dados são muito mais raramente, em seguida, lê.

A questão é: que tipo de modelo de dados hierárquica é mais adequado para tal situação. O projeto é baseado no framework Django e é peculiaridades (admin i-face, modelos de manipulação ...) devem ser considerados.

Muito obrigado!

Answer 1

Nested sets são melhores para o desempenho, se você não precisa de atualizações freqüentes ou ordenação hierárquica.

Se você precisa tanto atualizações de árvores ou ordenação hierárquica, é melhor modelo de dados uso parent-child.

É facilmente construído em Oracle e SQL Server 2005+, e não tão facilmente (mas ainda possível) em MySQL.

Answer 2

Gostaria de usar o algoritmo Preorder Árvore Traversal Modified, MPTT, para este tipo de dados hierárquicos. Isto permite um excelente desempenho em percorrer a árvore e encontrar as crianças, se você não se importa um pouco de uma penalidade sobre alterações na estrutura.

Felizmente Django tem uma grande biblioteca disponível para isso, django-mptt . Eu usei isso em um número de projectos com muito sucesso. Há também django-treebeard que oferece vários algoritmos alternativos, mas eu não usei (e não parece tão popular como mptt de qualquer maneira).

Answer 3

De acordo com estes artigos:

http://explainextended.com/ 2009/09/24 / adjacência-list vs-nested-sets-postgresql / http://explainextended.com/2009/09 / 29 / adjacência-list-vs-nested-sets-mysql /

"MySQL é o único sistema dos quatro grandes (MySQL, Oracle, SQL Server, PostgreSQL) para o qual os conjuntos aninhados modelo mostra desempenho decente e pode ser considerada como dados hierárquicos armazenados."

Answer 4

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

Answer 5

A lista de adjacência é muito mais fácil de manter e conjuntos aninhados são muito mais rápidos para consulta.

O problema sempre foi que a conversão de uma Lista de Adjacência para conjuntos aninhados tomou forma de tempo graças a um método realmente desagradável "pilha push" que é carregado com RBAR. Então, as pessoas acabam fazendo alguma manutenção muito difícil em conjuntos aninhados ou não usá-los.

Agora, você pode ter seu bolo e comê-lo também! Você pode fazer a conversão de 100.000 nodesin menos de 4 segundos e em um milhão de linhas em menos de um minuto! Tudo em T-SQL, pelo caminho! Por favor, consulte os seguintes artigos.

Hierarquias em esteróides # 1: Converter uma lista de adjacência para Nested Define

Hierarquias em esteróides # 2: A substituição para Nested Define Cálculos