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.
| Tags | Software Development Libraries |
|---|---|
| Operating Systems | OS Independent |
| Implementation | C++ |
Recent releases
- 07 Sep 2008 23:47
Changes: 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
Changes: All issues with reverse_iterators not working properly and one harmless bad-memory access were fixed.
- 26 Jan 2008 03:09
Changes: 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.
- 14 May 2007 04:21
Changes: 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.
- 27 Apr 2007 09:00
No changes have been submitted for this release.
