B+ Tree Data Structure in Erlang

Question

Is there any open source known implementation of the B+ Tree Data Structure in Erlang ?

Answer 1

I would definitely recommend looking into the eleveldb application if you really need a B+ tree. The point being that you want to store data in leaves of a tree, off-line on disk, as this is where B+-trees are normally an option. There is also a variant in pure Erlang of LevelDB called hanoidb which also is pretty nice, written by Kresten Krab Thorup. Same area of use.

If you need in-memory storage, you should be looking at either ETS or Mnesia (the latter for distribution). In Erlang these tend to be the fastest solutions as you have the advantage of never hitting the disk. It is especially true if you can do standard key/value lookups on your data with no need to run inside the transactional context in Mnesia (doing dirty-reads). Typical lookup speed is then 5-10 nanoseconds.

Answer 2

Just an alternative if you don't want to hack into open source database systems:

Chris Okasaki's Purely Functional Data Structures can give you some insight on implementing it by yourself. B+ tree itself is not that complicated from my experience.

I would recommend using gb_trees if you want both in-memory storage and something more low-level (in some sense) than ets and mnesia.

Answer 3

There is not a stand-alone library available that I know of. However the CouchDB source code is very readable and well implemented.