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

c++ c data-structures b-tree
Laurynas Biveinis picture Laurynas Biveinis · Nov 12, 2009 · Viewed 20.6k times · Source

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

Vijay Mathew picture Vijay Mathew · Nov 12, 2009

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)

Related questions

Visual C++ equivalent of GCC's __attribute__ ((__packed__))

For some compilers, there is a packing specifier for structs, for example :: RealView ARM compiler has "__packed" Gnu C Compiler has "__attribute__ ((__packed__))" Visual C++ has no equivalent, it only has the "#pragma pack(1)" I need something that I can …

Read More
Trie implementation

Is there any speed- and cache-efficient implementations of trie in C/C++? I know what a trie is, but I don't want reinvent the wheel, implementing it myself.

Read More
error: pointer to incomplete class type is not allowed

I am stumped at this step while implementing a ternary tree: #include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct tnode *Tptr; typedef struct node { char splitchar; Tptr lokid,eqkid,hikid; }Tnode; …

Read More