Released another updated version 0.8.3 of the STX B+ Tree C++ Template Classes package. The updated release fixes up issues with the root node == NULL when the tree is initially empty.

Fixed crash when running verify() on an empty btree object. Now the root node is freed when the last item is removed. Also fixed crash when attempting to copy an empty btree or when trying to remove a non-existing item from an empty btree.

Also enhancing the speedtest to test the hash table container implementation from __gnu_cxx. Extending tests by another set of runs measuring only the find/lookup functions. See the speed results web page for more information.

The updated source code package is available for download from this webpage.

Some compiled binaries of wxBTreeDemo for Win32 and Linux are available on the demo download page.

As before, the updated main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.

Released an updated version 0.8.2 of the STX B+ Tree C++ Template Classes package. The updated release fixes up all issues with iterators and one harmless bad-memory access.

The reverse_iterator classes of the B+ tree were completely reworked. Now they are real implementations and do not use STL magic. Both reverse_iterator and const_reverse_iterator should work as expected now. Added two large test cases for iterators. Enabled public default-constructors on iterators.

Also fixed a memory access bug which happens in erase_one_descend(): leaf->slotkey[leaf->slotuse - 1] if leaf-slotuse == 0. This doesn't have any other bad effect, because the case only occurs when leaf == root and then the resulting btree_update_lastkey message is never really processed. However it still is a bad-memory access.

The updated source code package including the wxBTreeDemo source is available for download from this webpage.

Some compiled binaries of wxBTreeDemo for Win32 and Linux are available on the demo download page.

As before, the updated main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.

Released a bugfix version 0.8.1 of the STX B+ Tree C++ Template Classes package. The bug fixed is a possibly illegal memory access during find() function.

I received a new test case via email in which valgrind detected an uninitialized memory access. By tracing it, I soon found that it happens during any find(key) call with a key that is larger than any item contained in the tree. During the find() function find_lower() is called on a leaf node and returns the slot number with the smallest or equal key. However if the queried key is larger than all keys in a leaf node or in the whole tree, find_lower() returns a slot number past the last valid key slot. Comparison of this invalid slot with the queried key then yields an uninitialized memory error in valgrind.

The updated source code package including the wxBTreeDemo source is available for download from this webpage.

Some compiled binaries of wxBTreeDemo for Win32 and Linux are available on the demo download page.

As before, the updated main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.

Released an updated version 0.8 of the STX B+ Tree C++ Template Classes package. The update fixes a few segmentation faults with empty trees without root node.

This new release includes 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 selected 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 MacOSX.

The source code package including the wxBTreeDemo source is available for download from this webpage.

Some compiled binaries of wxBTreeDemo for Win32 and Linux are available on the demo download page.

As before, the only slightly changed main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.

Released the first version 0.7 of the STX B+ Tree C++ Template Classes package. The template classes are licensed under the LGPL.

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.

The main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.

The source code package is available for download from this webpage.

The classes are documented extensively using doxygen. The generated HTML documentation can be browsed online or downloaded.

Special interest was put into performing a speed comparison test between the standard red-black tree and the new B+ tree implementation. The speed test results are interesting and show the B+ tree to be significantly faster for trees containing more than 16,000 items.