: elenco di adiacenza vs set nidificati

Question

Ho un catalogo prodotti. Ogni categoria è composta da un numero diverso (in profondità) di sottocategorie. Il numero di livelli (in profondità) è sconosciuto, ma sono abbastanza sicuro che non superi i 5,6 livelli. Le modifiche dei dati sono molto più raramente quindi vengono lette.

La domanda è: quale tipo di modello di dati gerarchici è più adatto per tale situazione. Il progetto è basato sul framework Django e le sue peculiarità (admin i-face, gestione dei modelli ...) dovrebbero essere considerate.

Grazie mille!

Answer 1

Nested sets sono migliori per le prestazioni, se non sono necessari aggiornamenti frequenti o ordini gerarchici.

Se sono necessari aggiornamenti degli alberi o ordini gerarchici, è preferibile utilizzare il modello di dati parent-child.

È facilmente costruito in Oracle e SQL Server 2005+ e non così facilmente (ma ancora possibile) in MySQL.

Answer 2

Vorrei utilizzare l'algoritmo Modified Preorder Tree Traversal, MPTT, per questo tipo di dati gerarchici. Questo permette grandi prestazioni nel percorrere l'albero e trovare bambini, se non ti dispiace un po 'di penalità nei cambiamenti alla struttura.

Fortunatamente Django ha una grande libreria disponibile per questo, django-mptt. Ho usato questo in un numero di progetti con molto successo. C'è anche django-treebeard che offre diversi algoritmi alternativi, ma non l'ho usato (e non sembra comunque popolare come mptt).

Answer 3

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

Answer 4

Secondo questi articoli:

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 è l'unico sistema di quattro grandi (MySQL, Oracle, SQL Server, PostgreSQL) per i quali i set nidificati il modello mostra prestazioni decenti e può essere considerato per memorizzare i dati gerarchici. "

Answer 5

L'elenco di adiacenza è molto più semplice da gestire e gli insiemi nidificati sono molto più veloci da interrogare.

Il problema è sempre stato che la conversione di un elenco di adiacenze in insiemi nidificati ha richiesto molto tempo grazie a un metodo "push stack" davvero brutto caricato con RBAR. Quindi le persone finiscono per fare qualche manutenzione davvero difficile in Nested Sets o non usarle.

Ora puoi avere la tua torta e mangiarla anche tu! Puoi effettuare la conversione su 100.000 nodi in meno di 4 secondi e su un milione di righe in meno di un minuto! Tutto in T-SQL, a proposito! Si prega di consultare i seguenti articoli.

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

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