Équivalent purement fonctionnel de B-Tree?

14

J'explore l'idée d'écrire un SGBD de manière purement fonctionnelle. La structure de données traditionnelle utilisée pour l'indexation est B-Tree. J'aimerais connaître un équivalent purement fonctionnel de B-Tree qui serait optimisé pour minimiser l'accès au disque. Merci.

ds.data-structures functional-programming db.databases Tianyi Cui
la source

Je ne sais pas grand-chose à ce sujet, mais cela semble être un point de départ raisonnable.

Ritwik Bose

Mechko, je pense que les structures de données sans cache ne sont généralement pas adaptées aux implémentations purement fonctionnelles.

jbapple

10

J'en sais plus sur les structures de données purement fonctionnelles que sur les structures de données à mémoire externe, mais je vais essayer.

$O(\log_B n)$ $O(B)$ $O(1)$

$O(\lg w)$ $w$

Vous voudrez peut-être regarder cette présentation sur RethinkDB , qui utilise des structures de données purement fonctionnelles en raison du coût des écritures sur les SSD.

jbapple
la source

4

Si vous êtes intéressé à écrire une base de données purement fonctionnelle, vous devriez probablement consulter la thèse de doctorat de Phil Trinder sur ce sujet. Il a un chapitre sur l'utilisation des B-Trees.

Dominic Mulligan
la source

Équivalent purement fonctionnel de B-Tree?

Réponses: