Che cos’è il modello di set nidificato?

Il modello di insiemi nidificati è anche noto come algoritmo di attraversamento dell’albero di preordine modificato ed è un modo per archiviare dati gerarchici all’interno di database relazionali. Questo modello ha il vantaggio di fornire un accesso molto veloce ed è meglio implementato nelle gerarchie che vengono lette più frequentemente di quelle in cui vengono scritte. A ciascun nodo all’interno del modello di informazioni vengono assegnati due numeri che vengono memorizzati come attributi. L’interrogazione del modello di set nidificato è abbastanza semplice perché entrambi i valori possono essere utilizzati per estrarre i dati necessari. Effettuare inserimenti, eliminazioni, spostamenti e aggiornamenti, tuttavia, è molto più complicato perché potrebbe comportare la rinumerazione dei nodi.

Tipicamente utilizzato per rappresentare insiemi nidificati o informazioni gerarchiche sotto forma di alberi, il modello di insiemi nidificati è stato introdotto da Joe Celko. Un albero, in questo caso, è una struttura di dati che contiene un numero di nodi collegati. Ad esempio, un nodo padre può connettersi a diversi nodi figlio e questa struttura viene ripetuta attraverso l’albero attraverso diversi livelli.

Gli alberi sono un ottimo modo per archiviare le informazioni in un ordine particolare all’interno di un database relazionale, che è un set di dati che memorizza i dati in base a caratteristiche comuni. Ad esempio, le informazioni sui prodotti all’interno della sezione alimentare di un negozio possono iniziare con il cibo, ramificandosi in frutta, verdura e carne. I frutti possono essere ulteriormente suddivisi in bacche, meloni e mele e le verdure in tuberi, verdure e altri, e la carne in maiale, montone e vitello.

Un database relazionale memorizza tutte queste informazioni in una forma di facile comprensione e un modello di insiemi nidificati consente di gestire in modo efficiente la struttura ad albero. Usando l’esempio sopra, il nodo radice sarebbe cibo, che è rappresentato da due valori. Dato il valore sinistro per il cibo pari a 1, agli altri elementi nell’albero viene assegnato un numero a sinistra in ordine. I frutti avrebbero un valore di 2 a sinistra, le bacche 3 e così via. I valori vengono quindi assegnati sul lato destro, lavorando lungo l’albero, dal basso verso l’alto, attraverso ogni ramo fino a quando l’ultimo valore viene assegnato al cibo sul lato destro.

Ogni elemento nell’albero finisce con due valori, diciamo lft per sinistra e rgt per destra, che possono essere usati per identificarli e indicare la loro relazione con altri elementi. Ad esempio, se i frutti hanno un valore di 2 e 15, allora tutti i nodi che hanno valori a sinistra maggiori di 2 e valori a destra inferiori a 15 sono discendenti dell’albero da frutto 2–15. Diventa facile estrarre informazioni su tutti i frutti in una volta perché questi valori possono essere specificati in una singola query al database.

Questo modello è eccellente per memorizzare informazioni a cui si accede spesso, ma gli inserimenti, le eliminazioni e il riordino delle informazioni nel modello di insiemi nidificati diventano molto noiosi. La riscrittura degli indici e la rinumerazione delle informazioni può causare l’arresto anomalo del database, soprattutto se l’albero cresce fino a includere centinaia di migliaia di nodi. Il modello nidificato è il migliore per i sistemi di gestione dei contenuti leggeri che hanno inserimenti e modifiche minimi. Gli inserimenti possono essere effettuati molto più velocemente nel modello a intervalli nidificati perché memorizza la posizione di ciascun nodo nell’albero utilizzando decimali a virgola mobile e codifica anche le informazioni sul percorso.