Discussion

What are skiplists good for?

ahartmetz: Skiplists have some nice properties - the code is fairly short and easy to understand, for one. Qt's QMap used to be skip list based, here's the rationale given for it: https://doc.qt.io/archives/qq/qq19-containers.html#associati...

mrjn: skiplists form the basis of in-memory tables used by LSM trees, which are themselves the basis of most modern DBs (written post 2005).

locknitpicker: FTA:> Skiplists to the rescue! Or rather, a weird thing we invented called a “skiptree”…I can't help but wonder. The article makes no mention of b-trees if any kind. To me, this sounded like the obvious first step.If their main requirement was to do sequential access to load data, and their problem was how to speed up tree traversal on an ad-hoc tree data structure that was too deep, then I wonder if their problem was simply having tree nodes with too few children. A B+ tree specifically sounds to be right on the nose for the task.