An interesting data structure with search time O(sqrt n)

[Sriram Srinivasan via Digitalmars-d]

The key search phrase is "cache oblivious data structures". One 
of the cache-friendly layouts is the van Emde Boas tree.