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
- 18 May 2011 12:49
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 03: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.
- 14 May 2007 04:21
Release Notes: 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.
Heartbeat
- Popularity Score
- 93.04
- Vitality Score
- 6.23
- Subscriptions
- 15
