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

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 3:29 PM, Dmitry Olshansky wrote:
> Reminds me of Van Emde Boas layout which is however fractal in nature:
> sqrt(N) pieces each having sqrt(N) element are subdivided again into
> sqrt(sqrt(N)) pieces and so on.
>
> Not sure if you have seen, but see also cache-oblivious data-structures:
> http://erikdemaine.org/papers/BRICS2002/paper.pdf

Thanks, I'll look these up! -- Andrei