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.
