[nkurz]

The memory accesses of a binary search look pretty much like complete random access

Why would this be? I would think that even in a naive implementation the fan-out is high enough that top levels of the B+ tree will always be in cache, so that you are only hitting RAM for the last level or two and the leaf. For in memory use, I thought the usual argument against binary search was (as 'elbee' mentions) the poor branch predictability, not the caching.