Open Source C++ B+ Tree Implementation

Template based B+ Tree

B+ Tree is a type of tree, which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a 'block' or 'node'). In a B+ tree, in contrast to a B-tree, all records are stored at the lowest level of the tree; only keys are stored in interior blocks.

For theory which lies behind implementation please refer to:

http://en.wikipedia.org/wiki/B+_tree
http://en.wikipedia.org/wiki/B-tree

Notes on implementation

This project goal was to create simple and yet very efficient template based B+ Tree implementation which supports different types of storage.

Implemented in C++, B+ Tree is template based, so it can be used with any type of data.

To change storage type (e.g. from file based to memory based) all you need is to change template argument of the BTreeAlgorithms class.

There are two controllers exist for such purpose: StreamBTreeController and RamBTreeController. You can write your own controller by simply changing logic in couple of methods within exiting controllers.

Two search methods available in the btree implementation:

First method is performed in the typical manner, starting at the root, the tree is traversed top to bottom, choosing the child pointer whose separation values are on either side of the value that is being searched.

Second method is more sophisticated and flexible. Different parameters of search can be set up by user, including starting point and method which will test each next new value. For example, using this type of search user can make efficient wildcard search on a string based btree, by simply writing wildcard test function and performing search in the btree.

The btree supports iteration through class BTreeIterator and data retrieval through class BTreeContainer which can be customized as STL based or some user defined data structure based one.
Several examples of using B+ Tree are provided.

Read More...

Comments

Post Your Comment:

Your Name:*

e-mail ID:(required for notification)*

Image Verification: 

 

 Subscribe