Gerarchici I modelli dati: adiacenza Lista vs. insiemi nidificati

Question

Ho un catalogo prodotti. Ogni categoria si compone di numero diverso (in profondità) di sottocategorie. Il numero di livelli (profondità) non è nota, ma sono abbastanza sicuro che non sarà supera di 5,6 livelli. Le modifiche dei dati sono molto più raramente quindi legge.

La domanda è: che tipo di modello di dati gerarchici è più adatto per tale situazione. Il progetto si basa sul framework Django ed è peculiarità (Admin i-face, modelli di movimentazione ...) dovrebbe essere considerato.

Molte grazie!

Answer 1

Nested sets sono migliori per le prestazioni, se non hai bisogno di aggiornamenti frequenti o ordine gerarchico.

Se avete bisogno di entrambi gli aggiornamenti degli alberi o ordine gerarchico, è meglio utilizzare il modello di dati parent-child.

E 'facilmente costruito nel Oracle e SQL Server 2005+, e non così facilmente (ma ancora possibile) in MySQL.

Answer 2

Vorrei utilizzare l'algoritmo Preorder albero Traversal Modified, MPTT, per questo tipo di dati gerarchici. Questo permette grandi prestazioni sul attraversare l'albero e trovare i bambini, se non ti dispiace un po 'di una sanzione modifiche alla struttura.

Per fortuna Django ha una grande biblioteca a disposizione per questo, django-MPTT . Ho usato questo in una serie di progetti con un sacco di successo. C'è anche django-Barbalbero che offre diversi algoritmi alternativi, ma non ho usato (e non sembra così popolare come MPTT comunque).

Answer 3

In base a questi articoli:

http://explainextended.com/ 2009/09/24 / liste di adiacenza-vs-nested-set-postgresql / http://explainextended.com/2009/09 / 29 / liste di adiacenza-vs-nested-set-mysql /

"MySQL è l'unico sistema di quattro grandi (MySQL, Oracle, SQL Server, PostgreSQL) per i quali il set di modello nidificato mostra prestazioni decenti e può essere considerato ai dati gerarchici memorizzati".

Answer 4

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

Answer 5

La lista di adiacenza è molto più facile da mantenere e set nidificati sono molto più veloce per interrogare.

Il problema è sempre stato che la conversione di un lista di adiacenza al set nidificate ha preso modo per lunghi grazie ad un metodo veramente brutto "stack push" che è caricato con rbar. Così la gente finisce per fare un po 'di manutenzione davvero difficile in Imposta nidificate o non li utilizzano.

Ora, si può avere la botte piena e la moglie ubriaca, troppo! Si può fare la conversione su 100.000 nodesin meno di 4 secondi e su un milione di righe in meno di un minuto! Tutto in T-SQL, tra l'altro! Si prega di consultare i seguenti articoli.

gerarchie sugli steroidi # 1: Convertire una lista di adiacenza alla nidificato Imposta

gerarchie sugli steroidi # 2: Un sostituto per i set nidificati calcoli