STX B+ Tree Revisiting Binary Search

While developing another piece of software, I happened to require a customizable binary search implementation, which lead me to revisit the binary search function of my quite popular STX B+ Tree implementation.

The binary search is a central component in the container, both for performance and correctness, as it is used when traversing the tree in search for a key or an insertion point. It is implemented in the find_lower() (and find_upper()) functions.

In a first step, I cleaned the implementation to use an exclusive right boundary. In this binary search variant, hi points to the first element beyond the end (with the same meaning as usual end() C++ iterator). This got rid of the special case handled after the while loop. The exclusive right boundary is also a more natural implementation variant (even though most computer science textbooks contain the inclusive version).

Having thus changed the binary search, I reran the speed tests. However, to my surprise, the performance of the library decreased slightly, but consistently. See the code diff 39580c19 and resulting speed test PDF, where solid lines are after the patch and dashed ones before.

After some research, I found a good, independent study of binary search variants by Stephan Brumme. His summary is that a linear scan is more efficient than binary search, if the keys are located in only one cache line. This (of course) explained the performance decrease I measured, as my "special case" after the search was in fact a very short linear scan of two element.

This lead me to experiment with different thresholds for switching between binary searches and linear scans. Again to my surprise, for the integer tests done by the speed test, binary search was never faster for 256 bytes nodes (64 integers, the default the library picked). Linear scanning was always quicker for these small nodes, even though a single cache line is only 64 bytes. Some further testing verified that indeed 256 bytes seems to be a sweet spot.

Thus I completely replaced the binary search in STX B+ Tree with a linear scan for all nodes up to 256 bytes. See below for the speed boost this gave.

However, that is not the whole story. Of course, the tree must still be usable with other keys than integers! In the default configuration, the library will try to create nodes of 256 bytes size, packing as many keys as necessary. For very large keys, however, at least 8 key items will be put into a node.

For these configurations, the tree will still use binary search. The same must be done if the comparison function is slow, as linear search has O(n) complexity where binary search does only O(log n) comparisons. For such occasions, the library exports a setting binsearch_threshold in the traits class, which can also be set to zero.

The following image shows the difference for integer search using binary search (dashed lines) and linear scan (solid lines):

For more information, click on the plot above or download the whole result data. The linear scan patch will be included in the next release of STX B+ Tree, which is due any day.