[rw]

I've read this page before, and again today, and I still don't understand how these unrolled lists are supposed to work in practice.

Based on the author's example at https://i.imgur.com/FYpPQPh.png, how do you take an unrolled skiplist that has a bottom row like this:

    [1,2,3] -> [4,5,_] -> [7,8,9]

And insert 2.5? An inevitable tree restructuring would have to occur, which vastly complicates the insertion logic.

[eternalban]

That first chunk will get split, 3 will get copied to new chunk, and list is restructured. I think the selling point here is you paid this price but get dividends on reduced cache misses in the future.

[rw]

Interesting. Whether that approach is efficient depends entirely on the workload. That complicates the analysis. (And one of the major benefits of skiplists is that the analysis is supposed to be simple.)