skip list vs btree

[CeleritasCelery]

I have been wondering what made you decide to use a skip list over a b-tree (like all other rope implementations)? Conceptually they are similar and achieve the same goals, but I am curious how you view the tradeoffs.

As I see it, skip lists have a better "best case" performance (the node you are looking for is the first one in the list) and worse "worst case" performance (you might have to execute the maximum number of skips to get there). whereas b-trees have average performance (you always need to descend to the leafs). The more you bias your RNG (i.e. the bigger the gap between nodes of height N) the more it exasperates the gap between best case and worst case.

it seems like certain things would be easier with a skiplist, such as splicing and iteration. But other things seem more complicated (and expensive), such as insertion.

curious why you chose skip lists. Doesn't seem to be a very common data structure.

[norcalli]

Skip lists are tight. Much simpler, which makes it easier to tweak to your specific workload w.r.t. cache, iteration, and supported operations. They also tend to be lower on CPU ops per operation I think.

Here's a blog by the author of TiKV that says some more useful stuff https://ticki.github.io/blog/skip-lists-done-right/