data-structures - que - persistencia wikipedia

Eficientes estructuras de datos persistentes 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, periódicos y demás?

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

Answer 1

Es sencillo modificar el omnipresente árbol B para que sea 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 los lenguajes funcionales para implementar, por ejemplo, 2-3 árboles.

Answer 2

SQLite tiene una implementación de estructura de datos de b-tree que puedes ver;

Answer 3

Implementé 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.

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 uno ordinario (efímero).