Equivalente puramente funcional da árvore B?

14

Estou explorando a idéia de escrever um DBMS de maneira puramente funcional. A estrutura de dados tradicional usada para indexação é a B-Tree. Gostaria de saber algum equivalente puramente funcional do B-Tree que seria otimizado para minimizar o acesso ao disco. Obrigado.

ds.data-structures functional-programming db.databases Tianyi Cui
fonte
Eu não sei muito sobre isso, mas este parece ser um lugar razoável para começar.
Ritwik Bose
Mechko, acho que estruturas de dados alheias ao cache geralmente não são passíveis de implementações puramente funcionais.
Jbapple

Respostas:

10

Eu sei mais sobre estruturas de dados puramente funcionais do que estruturas de dados de memória externa, mas vou tentar.

Uma árvore B pode ser escrita de maneira puramente funcional através da cópia do caminho. O caminho será curto ( ), mas a cópia de cada bloco exige que O ( B ) escreva nos blocos O ( 1 ) .O(registroB⁡n)O(B)O(1)

Se você deseja permitir que a estrutura seja totalmente persistente, e não puramente funcional, acho que você pode reduzir o número de gravações em uma cópia do nó para esperado amortizado, onde w é a largura da palavra, usando o matrizes totalmente persistentes em "Tentativas Confluentemente Persistentes para Controle de Versão Eficiente"O(lg⁡W)W

Você pode assistir a esta apresentação sobre o RethinkDB , que usa estruturas de dados puramente funcionais devido ao custo de gravações em SSDs.

jbapple
fonte
4

Se você estiver interessado em escrever um banco de dados puramente funcional, provavelmente deve conferir a tese de doutorado de Phil Trinder, que tratava desse assunto. Ele tem um capítulo sobre o uso de árvores B.

Dominic Mulligan
fonte