Projects / STX B+ Tree

STX B+ Tree

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.

Operating Systems

Recent releases

  •  06 May 2013 21:58

    Release Notes: This release applies accumulated patches and ideas: changing find_lower() to not use binary search for small node sizes, implementing bulk_load() to construct a B+ tree from a pre-sorted iterator range, replacing copy loops with std::copy calls, and changing the template header source code license to Boost Software License. Overall, these modifications yield a notable performance boost.

    •  18 May 2011 11:06

      Release Notes: A missing STL function, erase(iterator iter), was implemented. Support was added for STL allocators as template parameters. A bug when shifting pairs from left to right leaf nodes during deletion was fixed. Speed tests were run again on up-to-date hardware.

      •  07 Sep 2008 23:47

        Release Notes: All issues with root node pointer == NULL have been fixed. A crash when attempting to copy-construct an empty btree or when trying to remove a nonexistent item from an empty btree has been fixed. A crash when running verify() on an empty btree object has been fixed. Now the root node is freed when the last item is removed.

        •  14 Aug 2008 14:34

          Release Notes: All issues with reverse_iterators not working properly and one harmless bad-memory access were fixed.

          •  26 Jan 2008 11:09

            Release Notes: This release fixed a possibly illegal memory access during a find() or derived lookup call, if the queried key is larger than any item contained in the tree.


            Project Spotlight


            A Fluent OpenStack client API for Java.


            Project Spotlight

            TurnKey TWiki Appliance

            A TWiki appliance that is easy to use and lightweight.