3 ms·
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 exam
by rw 10y ago
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 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 10y agoThat 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 10y agoInteresting. 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.)