Ask HN: What are some cool but obscure data structures you know about?
Cache-Oblivious Data Structures: <a href="https:&#x2F;&#x2F;cs.au.dk&#x2F;~gerth&#x2F;MassiveData02&#x2F;notes&#x2F;demaine.pdf" rel="nofollow">https:&#x2F;&#x2F;cs.au.dk&#x2F;~gerth&#x2F;MassiveData02&#x2F;notes&#x2F;demaine.pdf</a><p>A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency&#x2F;cost of data access as the data size grows. This can&#x27;t be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way.<p>A way to think about it is that a CPU core is like a central point with &quot;rings&quot; of data arranged around it in a more-or-less a flat plane. The L1 cache is a tiny ring, then L2 is a bit further out physically and <i>has a larger area</i>, then L3 is even bigger and further away, etc... all the way out to permanent storage that&#x27;s potentially across the building somewhere in a disk array.<p>In essence, as data size &#x27;n&#x27; grows, the random access time grows as sqrt(n), because that&#x27;s the radius of the growing circle with area &#x27;n&#x27;.<p>Hence, a lot of algorithms that <i>on paper</i> have identical performance don&#x27;t in reality, because one of the two may have an extra sqrt(n) factor in there.<p>This is why streaming and array-based data structures and algorithms tend to be faster than random-access, even if the latter is theoretically more efficient. So for example merge join is faster than nested loop join, even though they have the same performance in theory.