¿Equivalente puramente funcional de B-Tree?

14

Estoy explorando la idea de escribir un DBMS de manera puramente funcional. La estructura de datos tradicional utilizada para la indexación es B-Tree. Me gustaría conocer un equivalente puramente funcional de B-Tree que se optimizaría para minimizar el acceso al disco. Gracias.

ds.data-structures functional-programming db.databases Tianyi Cui
fuente
No sé mucho al respecto, pero este parece ser un lugar razonable para comenzar.
Ritwik Bose
Mechko, creo que las estructuras de datos ajenas a la caché generalmente no son susceptibles de implementaciones puramente funcionales.
jbapple el

Respuestas:

10

Sé más sobre estructuras de datos puramente funcionales que estructuras de datos de memoria externa, pero lo intentaré.

O(Iniciar sesiónsi⁡norte)O(si)O(1)

O(lg⁡w)w

Es posible que desee ver esta presentación sobre RethinkDB , que utiliza estructuras de datos puramente funcionales debido al costo de las escrituras en SSD.

jbapple
fuente
4

Si está interesado en escribir una base de datos puramente funcional, probablemente debería consultar la tesis de doctorado de Phil Trinder sobre este mismo tema. Tiene un capítulo sobre el uso de B-Trees.

Dominic Mulligan
fuente