Struttura dati persistente

In ambito informatico, una struttura dati persistente è una struttura dati che quando viene modificata conserva sempre la versione precedente di se stessa: tali strutture dati sono di fatto immutabili in quanto le operazioni fatte su di esse non aggiornano in modo visibile la struttura in essere portando invece alla creazione di una nuova struttura aggiornata. Una struttura dati persistente non è da intendersi come una struttura dati memorizzata su una memoria persistente (permanente) come può essere un disco rigido: si tratta di un diverso significato del termine persistente.

Una struttura dati è parzialmente persistente se tutte le versioni possono essere accedute ma solo l'ultima può essere modificata. Una struttura dati è completamente persistente se tutte le versioni possono essere accedute e modificate. Se è anche possibile l'operazione di fusione che crea una nuova versione a partire da due versioni precedenti, la struttura dati viene chiamata confluentemente persistente. Le strutture dati che non sono invece persistenti vengono dette effimere.

Questi tipi di struttura sono particolarmente comuni in programmazione logica e in programmazione funzionale: in programmi puramente funzionali tutti i dati sono immutabili così da rendere le strutture dati completamente persistenti. Le strutture dati persistenti possono anche essere create aggiornando sul posto i dati e questi possono, in genere, richiedere meno tempo e spazio di memoria di massa dei loro corrispettivi puramente funzionali.

Anche se la persistenza può essere effettuata con la semplice copia, questa si rivela poco efficiente in termini di tempo e di spazio dato che molte operazioni producono solo piccoli cambiamenti in una struttura dati. Un metodo migliore consiste nello sfruttare le similarità tra le versioni vecchia e nuova in modo da condividere le parti comuni, quali ad esempio l'utilizzo dello stesso sotto-albero nelle strutture ad albero. Comunque, poiché spesso diventa non fattibile determinare quante versioni precedenti condividono le stesse parti della struttura e poiché spesso si vogliono scartare le vecchie versioni, si rende necessario un ambiente dotato del meccanismo di garbage collection.

La struttura persistente forse più semplice è la lista concatenata, una semplice lista di oggetti in cui ciascuno di essi ha un riferimento che punta a quello successivo nella lista. È persistente in quanto se ne può prendere la coda (costituita da un certo numero di voci) e aggiungere un nuovo nodo: la coda sarà così condivisa tra la vecchia e la nuova lista. Fintantoché le voci della coda resteranno immutabili, la condivisione sarà invisibile al programma.

Molte strutture dati basate sui puntamenti, come ad esempio gli RB-Albero e le code, possono essere facilmente adattate per creare strutture dati persistenti.

Collegamenti esterni

• Making Data Structures Persistent, su cs.cmu.edu.
• Persistent Data Structures (survey), su citeseerx.ist.psu.edu.
• Fully persistent arrays for efficient incremental updates and voluminous reads, su citeseerx.ist.psu.edu.
• Real-Time Deques, Multihead Turing Machines, and Purely Functional Programming, su citeseerx.ist.psu.edu.