estruturas de dados persistentes eficientes para banco de dados relacional

Question

Eu estou procurando material sobre estruturas de dados persistentes que podem ser usados ??para implementar um modelo relacional.

Persistência no sentido de estruturas de dados imutáveis.

Alguém sabe de alguns bons recursos, livros, papéis e tal?

(já tenho o livro Estruturas de Dados puramente funcional , que é um bom exemplo do que eu estou procurando.)

Answer 1

É fácil de modificar o onipresente B-tree ser persistente. Simplesmente sempre alloctate um novo nó sempre que um nó é modificado, e retornar o novo nó para o chamador recursiva, que irá inseri-lo nesse nível através da atribuição de um novo nó, etc. final do novo nó de raiz é retornado. N mais de O (N log N) nodos são atribuídos por operação.

Esta é a técnica utilizada em linguagens funcionais para implementar, por exemplo, 2-3 árvores.

Answer 2

Eu tenho implementado tal estrutura de dados um para BergDB ( http://bergdb.com/ ) - um banco de dados com um modelo de dados que é uma estrutura de dados persistente.

Gostaria de sugerir a leitura

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

É o trabalho original sobre como criar uma estrutura de dados persistente baseado em um ordinário (efémera).

Answer 3

SQLite tem uma implementação de estrutura de dados b-tree você pode dar uma olhada;