14
$\begingroup$

I am exploring the idea of writing a DBMS in purely functional way. The traditional data structure used for indexing is B-Tree. I'd like to know some purely functional equivalent of B-Tree that would be optimized to minimize disk access. Thanks.

$\endgroup$
  • $\begingroup$ I don't know much about it, but this seems like a reasonable place to start. $\endgroup$ – Ritwik Bose Jan 23 '11 at 1:11
  • $\begingroup$ Mechko, I think cache-oblivious data structures generally are not amenable to purely functional implementations. $\endgroup$ – jbapple Jan 23 '11 at 2:49
10
$\begingroup$

I know more about purely-functional data structures than external-memory data structures, but I'll give this a go.

A B-tree can be written in a purely-functional way by path copying. The path will be short ($O(\log_B n)$), but copying each block takes $O(B)$ writes in $O(1)$ blocks.

If you're willing to let the structure be just fully persistent, rather than purely functional, I think you can reduce the number of writes in a node copy to $O(\lg w)$ expected amortized, where $w$ is the word width, using the fully persistent arrays in "Confluently Persistent Tries for Efficient Version Control"

You might want to watch this presentation about RethinkDB, which uses purely-functional data structures because of the cost of writes in SSDs.

$\endgroup$
4
$\begingroup$

If you're interested in writing a purely functional database, you should probably check out Phil Trinder's PhD thesis which was on this very subject. He has a chapter on the use of B-Trees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.