Se avete mai dovuto salvare dei dati con una struttura ad albero in un database relazionale sapete che non è una cosa facile. O meglio, non è facile farlo e ottenere delle query performanti.
L'approccio più comune è quello di aggiungere un campo "padre" alla tabella con i nostri nodi. A quel punto sapere chi è nostro padre o chi siano i nostri fratelli è facilissimo... ma sapere se un nodo è nostro nonno o pronipote o sapere chi è il figlio maggiore richiedono nel primo caso di fare ricorsione con numerose query, e nel secondo di aggiungere e mantenere aggiornato un altro campo d'ordinamento. Questo approccio è comunemente noto come "adjacency model".
L'adjacency model non risolve molti problemi (a meno di usare lente query ricorsive) come ottenere il numero di discendenti di un nodo o eliminarli tutti, o ancora come ottenere il percorso dalla radice a un nodo. Una cosa in cui eccelle invece è lo spostamento di sottoalberi, molto performante.
Nested Set Model (e Baobab) alla riscossa.
Il Nested Set Model è una interessante alternativa all'adjacency model. Esso risolve i problemi evidenziati prima, aggiungendone alcuni altri (spesso aggirabili).
Nel Nested Set Model alle tabelle vengono aggiunti due campi, "sinistro" e "destro", che contengono un indice numerico: l'intervallo identificato da questi due valori permette di posizionare il nostro nodo all'interno dell'albero. Per esempio l'intervallo di un nodo è sempre racchiuso in quello di un suo antenato; o ancora, il percorso tra la radice e un nodo è formato da tutti i nodi il cui intervallo comprende l'indice sinistro del nodo di riferimento.
Ci vogliono tempo e immagini per spiegare come funziona questo modello, potete ottenere maggiori informazioni ad esempio alla relativa pagina su wikipedia.
Il punto è che questo modello permette di effettuare ricerche molto più in fretta che con quello tradizionale, anche se con algoritmi ben più complicati (e a fronte di alcune limitazioni: l'aggiunta di nodi è molto lenta e gli alberi non dovrebbero superare di molto il migliaio di nodi [ma con la possibilità di creare foreste]).
Baobab è una libreria (ad oggi solo per PHP e MySQL) per semplificare la creazione e gestione di un albero applicando il Nested Set Model. Il suo utilizzo è estremamente semplice, e garantisce un'ottima flessibilità. Infatti è possibile scegliere di utilizzare la sola interfaccia PHP oppure sfruttare le documentate procedure SQL per creare personali soluzioni di ricerca. Inoltre è open source e testata, caratteristiche che non ho trovato in molte alternative.
Potete sapere tutto sulla libreria nelle pagine ad essa dedicata, oppure andare a leggere il codice sorgente sul repository ufficiale
Buona lettura