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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I don't know much about it, but this seems like a reasonable place to start. $\endgroup$– Ritwik BoseCommented Jan 23, 2011 at 1:11
-
$\begingroup$ Mechko, I think cache-oblivious data structures generally are not amenable to purely functional implementations. $\endgroup$– jbappleCommented Jan 23, 2011 at 2:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Citeseer link seems unresponsive. The thesis is also here, $\endgroup$ Commented Jan 26, 2024 at 14:48