Estructuras de datos persistentes eficientes para la base de datos relacional

Question

Estoy buscando material sobre estructuras de datos persistentes que se puedan usar para implementar un modelo relacional.

Persistencia en el sentido de estructuras de datos inmutables.

¿Alguien sabe de algunos buenos recursos, libros, documentos y tal?

(que ya tienen el libro Purely Functional Data Structures, que es un buen ejemplo de lo que estoy buscando.)

Answer 1

Es sencillo modificar el omnipresente B-tree que ser persistente. Simplemente siempre asocie un nuevo nodo cada vez que se modifique un nodo, y devuelva el nuevo nodo al llamador recursivo, quien lo insertará en ese nivel asignando un nuevo nodo, etc. Finalmente, se devuelve el nuevo nodo raíz. No se asignan más nodos O (log N) por operación.

Esta es la técnica utilizada en lenguajes funcionales para implementar, por ejemplo, 2-3 árboles.

Answer 2

SQLite tiene un b-tree data structure implementation que puede consultar;

Answer 3

He implementado una estructura de datos para BergDB (http://bergdb.com/) - una base de datos con un modelo de datos que es una estructura de datos persistente.

que sugeriría leer

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

Es el trabajo original sobre cómo crear una estructura de datos persistente basado en un ordinario (efímera) uno.