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

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.