panthema / 2011 / 0518-STX-B+Tree-0.8.6-Update
Small drawing of a B+ tree

Update Release of STX B+ Tree 0.8.6

Posted on 2011-05-18 12:44 by Timo Bingmann at Permlink with 1 Comments. Tags: #c++ #stx-btree

After four years I have decided to release an updated version 0.8.6 of the STX B+ Tree C++ Template Classes package. The updated release contains all patches that have accumulated in my inbox over the years. So yes, please send me patches for this project, it is not in vain! Below the highlights on the changes in this release:

  • Implemented a missing function: erase(iterator iter) by recursively searching for the referenced leaf node inside the subtree containing equal keys.
  • Applied a patch which adds support for STL allocators as template parameters.
  • Corrected limits of a for loop when shifting pairs from left to right leaf nodes during deletion.

I also reran the speed test done back in 2007 on my new hardware and compared the results with the old data. Due to the larger L2 cache sizes in my new Intel Core i7, the B-tree speed-up first starts to show at about 100,000 integer items, rather than 16,000 items with my older Pentium 4. This might also have something to do with the new CPU using 64-bit pointers and thus requiring larger nodes for child references. Read the complete speed test here.

result plot from new speedtest

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

Comment by Brian Beuning at 2011-12-01 14:51 UTC

I am thinking a B-tree map would use less memory than std::map
since it has fewer pointers. Maybe a graph comparing memory usage would be interesting to your users.

Post Comment
E-Mail or Homepage:

URLs (http://...) are displayed, e-mails are hidden and used for Gravatar.

Many common HTML elements are allowed in the text, but no CSS style.