Plenty of databases use b+trees, which don't address this exact flavour of concern. In my direct experience, MySQL will perform quite poorly with lots of random

Plenty of databases use b+trees, which don't address this exact flavour of concern. In my direct experience, MySQL will perform quite poorly with lots of random lookups once your index starts getting to a meaty size.