Menu
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.
835
B-Trees are a variation on binary search trees that allow quick searching in files on disk. Instead of storing one key and having two children, B-tree nodes have n keys and n+1 children, where n can be large. This shortens the tree (in terms of height) and requires much less disk access than a binary search tree would.
B+ Tree is an extension of B Tree which allows efficient insertion, deletion and search operations. In B Tree, Keys and records both can be stored in the internal as well as leaf nodes. Whereas, in B+ tree, records (data) can only be stored on the leaf nodes while internal nodes can only store the key values.
Fan-out, in any tree, is number of pointers to child nodes in a node. Different trees have different fan-out. A binary tree has fanout 2. A B-tree has a fan-out B, with all nodes except leaves having between B/2 and B children.
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)
79
My own implementation is under http://www.die-schoens.de/prg License is Apache. Its disk-based, maps to shared memory where it also can do locking (i. e. multiuser), file format protects against crash etc. All of the above can be easily switched off (compile or runtime if you like). So bare bone would be almost ANSI-C, basically caching in ones own memory and not locking at all. Test program is included. Currently, it only deals with fixed-size fields, but I am working on that...
28
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
