BTree

An array based C-implementation of BTrees attempting a reasonable performance.

a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time -- Wikipedia

BTrees are -- algorithm wise -- implemented using pointers to subtrees which is horribly slow on hardware. This project aims to optimize this, by putting the whole struct into an array which can be iterated through in-order.

The implementation follows the algorithm described in CLRS.

Usage

// define a comparator function
int cmp_int(const void *a, const void *b) {
  return *(const int*)a - *(const int*)b;
}
...

// Create a new btree
// 16 is the "degree" of the tree, different sizes might pose better performance
// depending on the data you're storing
struct btree *tree = btree_new(sizeof(int), 16, &cmp_int);

// add values
int a = 42;
int b = 3;
int c = 13;

btree_insert(tree, &a);
btree_insert(tree, &b);
btree_insert(tree, &c);

{
  int searchkey = 42;
  // search returns a pointer to the internal elements, NULL if not found
  int *ret = btree_search(tree, &searchkey);
}

// free up the btree when you're done.
btree_free(&tree);

See the respective example branches for more examples.

Installation

You can run make lib to create a shared object file to which you can either link to and adding the directory of the .so file to your LD_LIBRARY_PATH environment variable, or move into /usr/lib. There's currently not a make target to install it system wide yet.