# STX B+ Tree Revisiting Binary Search

Posted on 2013-05-04 12:44 by Timo Bingmann at Permlink with 0 Comments. Tags: stx-btree

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.