All memory is O(log(n)) latency for cache misses, though. You really shouldn't need to worry about B Trees being used instead of hash maps or something like that. For joins, using sorted and even B Tree base data structures can even give asymptotic benefits due to being able to skip keyspace ranges, potentially even at higher levels of the B Tree.