STX B+ Tree 0.8

STX B+ Tree project is a set of C++ template classes implementing a B+ tree key/data container in main memory. The classes are designed as drop-in replacements of the STL containers set, map, multiset and multimap and follow their interfaces very closely. By packing multiple value pairs into each node of the tree the B+ tree reduces heap fragmentation and utilizes cache-line effects better than the standard red-black binary tree.
The tree algorithms are based on the implementation in Cormen, Leiserson and Rivests Introduction into Algorithms, Jan Janninks paper and other algorithm resources. The classes contain extensive assertion and verification mechanisms to ensure the implementations correctness by testing the tree invariants.
The main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments btree.h.
Special interest was put into performing a speed comparison test between the standard red-black tree and the new B+ tree implementation. The speed test results are interesting and show the B+ tree to be significantly faster.
Enhancements:
- This release introduces the demonstration program wxBTreeDemo.
- This program draws illustrations of the B+ trees constructed by the STX B+ Tree template classes.
- It allows the user to select different types of B+ tree instantiations: integer or string keys and different slot numbers.
- The user may insert and erase key/data pairs from the tree and run different search operations.
- The demo program uses the cross-platform wxWidgets toolkit and can be compiled on Linux, Windows, and Mac OS X.