Template based B+ Tree
Description
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.
Download
Dependencies
B+ Tree itself has no dependencies, but memory and file controllers depend on ScalingWeb IO Streams library.
License
This program is licensed under permissive BSD license which allows commercial use.
Feedback
Please send you feedback or comments to opensource@scalingweb.com
© 2007 ScalingWeb.com