I remember reading a blogpost about this, they compared binary search on integer keys with a highly-optimized unrolled SIMD linear search. The takeaway was tha

I remember reading a blogpost about this, they compared binary search on integer keys with a highly-optimized unrolled SIMD linear search. The takeaway was that the break-even point was suprising small - just tens of elements, which is crazy considering a CPU can do like 2x 8-wide AVX2 integer comparisons in a single cycle. Modern CPUs are just that good at executing branchy code. But with B-trees we can have the best of both worlds - trees with a relatively high branch factor, like 16, that can still be tested in one go using SIMD. Another advantage is cache locality - which is one of the reasons B-trees are favored when implementing filesystems - much of the tree doesn't need to be fetched into memory while the parts that do are contiguous in memory.