Looking for a disk-based B+ tree implementation in C++ or C

Question

Hi,

I am looking for a lightweight open source paging B+ tree implementation that uses a disk file for storing the tree.

So far I have found only memory-based implementations, or something that has dependency on QT (?!) and does not even compile.

Modern C++ is preferred, but C will do too.

I prefer to avoid full embeddable DBMS solution, because: 1) for my needs bare bone index that can use the simplest possible disk file organization is enough, no need for concurrency, atomicity and everything else. 2) I am using this to prototype my own index, and most likely will change some of the algorithms and storage layout. I want to do that with a minimum of effort. It's not going to be production code.

Answer 1

I' pretty sure it's not the solution you're looking but why don't you store the tree in a file yourself? All you need is an approach for serialization and an if/ofstream.

Basically you could serialize it like that: go to root, write '0' in your file a divider like '|', the number of elements in root and then all root elements. Repeat with '1' for level 1 and so on. As long as you don't change the level keep the level index, empty leafs could look like 2|0.

Answer 2

http://people.csail.mit.edu/jaffer/WB.

You can also consider re-using the B-Tree implementations from an open source embeddable database. (BDB, SQLite etc)

Answer 3

Faircom's C-Tree Plus has been available commercially for over 20 years. Don't work for them etc... FairCom

There is also Berkley DB which was bought by Oracle but is still free from their site.

Answer 4

You could look at Berkeley DB, its supported ny Oracle but it is open source and can be found here.

Answer 5

I second the suggestion for Berkeley DB. I used it before it was bought by Oracle. It is not a full relational database, but just stores key-value pairs. We switched to that after writing our own paging B-Tree implementation. It was a good learning experience, but we kept adding features until is was just a (poorly) implemented version of BDB.

If you want to do it yourself, here is an outline of what we did. We used mmap to map pages into memory. The structure of each page was index based, so with the page start address you could access any element on the page. Then we mapped and unmapped pages as necessary. We were indexing multi GB text files, back when 1 GB of main memory was considered a lot.