Another potentially useful data structure that has good asymptotic complexity, but probably also poor cache locality is the Van Emde Boas tree [0]. I've never seen one in practice, but they sure make for excellent p-set problems!

[0] https://en.wikipedia.org/wiki/Van_Emde_Boas_tree