STX B+ Tree C++ Template Classes

Original Application

The idea originally arose while coding a read-only database, which used a huge map of millions of non-sequential integer keys to 8-byte file offsets. When using the standard STL red-black tree implementation this would yield millions of 20-byte heap allocations and very slow search times due to the tree's height. So the original intension was to reduce memory fragmentation and improve search times. The B+ tree solves this by packing multiple data pairs into one node with a large number of descendant nodes.

In computer science lectures it is often stated that using consecutive bytes in memory would be more cache-efficient, because the CPU's cache levels always fetch larger blocks from main memory. So it would be best to store the keys of a node in one continuous array. This way the inner scanning loop would be accelerated by benefiting from cache effects and pipelining speed-ups. Thus the cost of scanning for a matching key would be lower than in a red-black tree, even though the number of key comparisons are theoretically larger. This second aspect aroused my academic interest and resulted in the speed test experiments.

A third inspiration was that no working C++ template implementation of a B+ tree could be found on the Internet. Now this one can be found.

Implementation Overview

This implementation contains five main classes within the stx namespace (blandly named Some Template eXtensions). The base class btree implements the B+ tree algorithms using inner and leaf nodes in main memory. Almost all STL-required function calls are implemented (see below for the exceptions). The asymptotic time requirements of the STL standard are theoretically not always fulfilled. However in practice this B+ tree performs better than the STL's red-black tree at the cost of using more memory. See the speed test results for details.

The base class is then specialized into btree_set, btree_multiset, btree_map and btree_multimap using default template parameters and facade functions. These classes are designed to be drop-in replacements for the corresponding STL containers.

The insertion function splits the nodes on recursion unroll. Erase is largely based on Jannink's ideas. See http://dbpubs.stanford.edu:8090/pub/1995-19 for his paper on "Implementing Deletion in B+-trees".

The two set classes (btree_set and btree_multiset) are derived from the base implementation class btree by specifying an empty struct as data_type. All functions are adapted to provide the base class with empty placeholder objects. Note that it is somewhat inefficient to implement a set or multiset using a B+ tree: a plain B tree (without +) would hold no extra copies of the keys. The main focus was on implementing the maps.

Problem with Separated Key/Data Arrays

The most noteworthy difference to the default red-black tree implementation of std::map is that the B+ tree does not hold key/data pairs together in memory. Instead each B+ tree node has two separate arrays containing keys and data values. This design was chosen to utilize cache-line effects while scanning the key array.

However it also directly generates many problems in implementing the iterators' operators. These return a (writable) reference or pointer to a value_type, which is a std::pair composition. These data/key pairs however are not stored together and thus a temporary copy must be constructed. This copy should not be written to, because it is not stored back into the B+ tree. This effectively prohibits use of many STL algorithms which writing to the B+ tree's iterators. I would be grateful for hints on how to resolve this problem without folding the key and data arrays.

Test Suite

The B+ tree distribution contains an extensive test suite using cppunit. According to gcov 91.9% of the btree.h implementation is covered.

STL Incompatibilities

Key and Data Type Requirements

The tree algorithms currently do not use copy-construction. All key/data items are allocated in the nodes using the default-constructor and are subsequently only assigned new data (using operator=).

Iterators' Operators

The most important incompatibility are the non-writable operator* and operator-> of the iterator. See above for a discussion of the problem on separated key/data arrays. Instead of *iter and iter-> use the new function iter.data() which returns a writable reference to the data value in the tree.

Erase Functions

The B+ tree supports only two erase functions:

The following STL-required functions are not supported:

Extensions

Beyond the usual STL interface the B+ tree classes support some extra goodies.

B+ Tree Traits

All tree template classes take a template parameter structure which holds important options of the implementation. The following structure shows which static variables specify the options and the corresponding defaults:

Speed Tests

The implementation was tested using the speed test sources contained in the package. For a long discussion please see the results web page within the documentation.

2008-09-07 - Timo Bingmann - v0.8.3

• speedtest.cc: Modifying speedtest to also test the hash table container implementation from __gnu_cxx. Extending tests by another set of runs measuring only the find/lookup functions.

2008-09-03 - Timo Bingmann - v0.8.3

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

2008-08-13 - Timo Bingmann - v0.8.2

• btree.h: Replacing many / 2 integer divisions with >> 1 as suggested by received e-mails. This may or may not improve speed. I personally doubt it, because modern compilers should optimize these simple instructions.

2008-08-01 - Timo Bingmann - v0.8.2

• btree.h: Completely reworked reverse_iterator classes. 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. Also enabling public Default-Constructor on iterators.

2008-08-01 - Timo Bingmann - v0.8.2

• btree.h: Fixing up a memory access bug which happens in leaf->slotkey[leaf->slotuse - 1] if leaf-slotuse == 0. This doesnt have any other bad effect, because the case only occurs when leaf == root and thus the btree_update_lastkey message is never really processed. However it still is a bad-memory access.

2008-01-25 - Timo Bingmann - v0.8.1

• btree.h: Fixed a valgrind-detected bug based on a new test case received via email. During the find() function find_lower() is called 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.

2007-05-12 - Timo Bingmann - v0.8

• btree.h: Fixed segfault in print() because of non-existing root. Fixed segfault in end() when the tree is totally empty. Added BTREE_FRIENDS macro so that wxBTreeDemo can access private members. Changing print function to output to a user-given std::ostream