Strutture dati permanenti efficienti per database relazionali

Question

Sto cercando materiale su strutture di dati persistenti che possono essere utilizzate per implementare un modello relazionale.

Persistenza nel significato di strutture di dati immutabili.

Qualcuno sa di alcune buone risorse, libri, documenti e simili?

(Ho già il libro Strutture di dati puramente funzionali , che è un buon esempio di ciò che sto cercando.)

Answer 1

È semplice modificare l'onnipresente B-tree in modo che sia persistente. Basta allocare sempre un nuovo nodo ogni volta che un nodo viene modificato e restituire il nuovo nodo al chiamante ricorsivo, che lo inserirà a quel livello allocando un nuovo nodo, ecc. Viene restituito il nuovo nodo radice. Non vengono assegnati più di O (log N) nodi per operazione.

Questa è la tecnica utilizzata nei linguaggi funzionali per implementare, ad esempio 2-3 alberi.

Answer 2

Ho implementato una tale struttura di dati per BergDB ( http://bergdb.com/ ) - un database con un modello di dati che è una struttura di dati persistente.

Suggerirei di leggere

http://www.cs.cmu.edu/~sleator/ carte / Persistence.htm

È il lavoro originale su come creare una struttura di dati persistente basata su una ordinaria (effimera).

Answer 3

SQLite ha una implementazione della struttura dei dati b-tree puoi dare un'occhiata a;