Estructuras de datos persistentes eficientes para la base de datos relacional

Question

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

Persistencia en el significado de estructuras de datos inmutables.

¿Alguien sabe de algunos buenos recursos, libros, documentos y demás?

(Ya tengo el libro Estructuras de datos puramente funcionales , que es un buen ejemplo de lo que estoy buscando).

Answer 1

Es sencillo modificar el B-tree para que sea persistente. Simplemente siempre asigne un nuevo nodo cada vez que se modifique un nodo, y devuelva el nuevo nodo a la persona que llama recursivamente, que lo insertará en ese nivel asignando un nuevo nodo, etc. Finalmente, se devuelve el nuevo nodo raíz. No se asignan más de O (log N) nodos por operación.

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

Answer 2

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

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 basada en una estructura ordinaria (efímera).

Answer 3

SQLite tiene una implementación de la estructura de datos b-tree puedes echar un vistazo;