4 ms·

This looks like a less efficient version of skip lists.

• jqpabc123 3y ago
  Skip lists are more complex, require more pointer storage and are really intended for more dynamic data. I would label this more of a hybrid hash/lookup table --- but without any wasted storage space. The key observation here is that on modern hardware, a simple, linear, fully cache based search of 20-30 elements is often faster than a binary search. If a pre-computed index can easily and efficiently narrow the average linear search range down to this level, it is likely to be faster. But re-arranging into Eytzinger order is sorta equivalent to building an index so as always, apply your own judgment.