The index itself is also a b-tree (unless if it is fully in memory). You also have to consider writes and reads in this index. There, locality also matters. Sure, not as much as with the data itself. But I have seen cases where the index lookup (with randomly distributed UUIDs) was the bottleneck, and not reading the rows. Even thought the row where 1 KB on average.