<p>If you're interested in writing a purely functional database, you should probably check out Phil Trinder's <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.4456" rel="nofollow">PhD thesis</a> which was on this very subject.  He has a chapter on the use of B-Trees.</p>

CC BY-SA 4.0
2024-01-26T14:48:45.537Z
Citeseer link seems unresponsive. The thesis is also [here](https://ora.ox.ac.uk/objects/uuid:1fa54dcc-1188-40c9-aa2f-ce2c989e7bd3/download_file?file_format=application%2Fpdf&safe_filename=603849251.pdf&type_of_work=Thesis),
Mohan Radhakrishnan
CC BY-SA 3.0
2011-10-05T09:57:39.280Z
2011-10-05T09:57:39.280Z
Dominic Mulligan
<p>I know more about purely-functional data structures than external-memory data structures, but I'll give this a go.</p>

<p>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.</p>

<p>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 <a href="http://erikdemaine.org/papers/ConfluentTries_Algorithmica/" rel="noreferrer">the fully persistent arrays in "Confluently Persistent Tries for Efficient Version Control"</a></p>

<p>You might want to watch <a href="http://www.youtube.com/watch?v=uDHc3lkr3Ns" rel="noreferrer">this presentation about RethinkDB</a>, which uses purely-functional data structures because of the cost of writes in SSDs.</p>

CC BY-SA 2.5
2011-01-23T03:03:19.540Z
2011-01-23T03:03:19.540Z
jbapple
<p>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.</p>

CC BY-SA 2.5
2011-01-23T01:11:54.573Z
I don't know much about it, but [this](http://www.cs.sunysb.edu/~bender/pub/cache-oblivious-btree.ps) seems like a reasonable place to start.
Ritwik Bose
CC BY-SA 2.5
2011-01-23T02:49:23.580Z
Mechko, I think cache-oblivious data structures generally are not amenable to purely functional implementations.
jbapple
<ds.data-structures><functional-programming><db.databases>
Purely Functional Equivalent of B-Tree?
Tianyi Cui
# Purely Functional Equivalent of B-Tree?

(Asked by: username_0 on 2011-01-22)

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.

**Tags:** ds.data-structures, functional-programming, db.databases
> **Comments:**
> **username_1**: I don't know much about it, but [this](http://www.cs.sunysb.edu/~bender/pub/cache-oblivious-btree.ps) seems like a reasonable place to start.  
> **username_2**: Mechko, I think cache-oblivious data structures generally are not amenable to purely functional implementations.  

---

## 2 answers

### Answer by username_2 on 2011-01-23. Score: 12 | Accepted answer

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"](http://erikdemaine.org/papers/ConfluentTries_Algorithmica/)

You might want to watch [this presentation about RethinkDB](http://www.youtube.com/watch?v=uDHc3lkr3Ns), which uses purely-functional data structures because of the cost of writes in SSDs.


---

### Answer by username_3 on 2011-10-05. Score: 4

If you're interested in writing a purely functional database, you should probably check out Phil Trinder's [PhD thesis](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.4456) which was on this very subject. He has a chapter on the use of B-Trees.

> **Comments:**
> **username_4**: Citeseer link seems unresponsive. The thesis is also [here](https://ora.ox.ac.uk/objects/uuid:1fa54dcc-1188-40c9-aa2f-ce2c989e7bd3/download_file?file_format=application%2Fpdf&safe_filename=603849251.pdf&type_of_work=Thesis),  

---

