È più semplice da spiegare con gli esempi che con poche parole. Considera l'albero dei campioni, memorizzando i nomi:
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
Percorso materializzato significa che ogni nodo memorizza il suo percorso completo codificato. Per esempio, è possibile memorizzare il suo indice utilizzando un punto come separatore
Name Path
William 1
Jones 1.1
Blake 1.2
Adams 1.2.1
Tyler 1.3
Joseph 2
Miller 2.1
Flint 2.2
Quindi, Adams conosce il suo nome completo è William Blake Adams, perché ha il percorso 1.2.1, indicando il nodo 1 al primo livello - William - al nodo 1.2 a livello 2 - Blake - e al nodo 1.2.1 a livello 3 - Adams.
Adjacency List significa che l'albero è memorizzato mantenendo un collegamento ad alcuni nodi adiacenti. Ad esempio, è possibile memorizzare chi è il genitore e chi è il fratello successivo.
Name Parent Next
William null Joseph
Jones William Blake
Blake William Tyler
Adams Blake null
Tyler William null
Joseph null null
Miller Joseph Flint
Flint Joseph null
Si noti che potrebbe essere semplice come solo la memorizzazione del genitore, se non abbiamo bisogno di tenere i bambini di un nodo ordinato. Ora Adams può ottenere tutti i suoi antenati in modo ricorsivo fino a zero per trovare il suo nome completo.
Set nidificati significa che ogni nodo viene archiviato con un indice, di solito un valore sinistro e uno destro, assegnato a ciascuno mentre si attraversa l'albero nell'ordine DFS, in modo da sapere che i suoi discendenti si trovano all'interno di tali valori. Ecco come i numeri sarebbero assegnate all'esempio albero:
1 William 10
2 Jones 3
4 Blake 7
5 Adams 6
8 Tyler 9
11 Joseph 16
12 Miller 13
14 Flint 15
e sarebbe archiviato come:
Name left right
William 1 10
Jones 2 3
Blake 4 7
Adams 5 6
Tyler 8 9
Joseph 11 16
Miller 12 13
Flint 14 15
Così, ora Adams riesce a trovare i suoi antenati di interrogazione che ha un basso a sinistra e un valore in alto a destra e ordinali per il valore di sinistra.
Ogni modello ha i suoi punti di forza e di debolezza. Scegliere quale utilizzare dipende in realtà dalla tua applicazione, dal database che stai usando e dal tipo di operazioni che farai più spesso. È possibile trovare un buon confronto here.
Il confronto menziona un quarto modello che non è molto comune (non conosco altre implementazioni ma la mia) e molto complicato da spiegare in poche parole: Intervallo nidificato tramite Matrix Encoding.
Quando si inserisce un nuovo nodo in un set nidificato, è necessario ri-enumerare tutti quelli che lo precedono nella traversata. L'idea dietro gli intervalli annidati è che esiste un numero infinito di numeri razionali tra due numeri interi, quindi è possibile memorizzare il nuovo nodo come frazione dei suoi nodi precedenti e successivi.Memorizzare e interrogare le frazioni può essere problematico, e questo porta alla tecnica di codifica a matrice, che trasforma quelle frazioni in una matrice 2x2 e molte operazioni possono essere eseguite da un'algebra di matrice che non è evidente a prima vista, ma può essere molto efficiente.
Treebeard ha implementazioni molto semplici di ciascuna di Percorso materializzato, Set nidificati e Elenchi di adiacenza, senza ridondanza. django-mptt usa effettivamente un mix di Nested Sets e Adjacency Lists, poiché mantiene anche un collegamento al genitore e può usarlo sia per interrogare i bambini in modo più efficiente, sia per ricostruire l'albero nel caso in cui venga incasinato da qualcuno.