The STX B+ Tree package 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 Rivest’s Introduction into Algorithms, Jan Jannink’s paper and other algorithm resources. The classes contain extensive assertion and verification mechanisms to ensure the implementation’s correctness by testing the tree invariants. To illustrate the B+ tree’s structure a wxWidgets demo program is included in the source package.
