Open Source C++ B+ Tree Implementation

Author: scalingweb.com | Published: 12th Jun 2008 | Visited: 1177 times | Add Comment
Filed in: CPlusPlus

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 Article