[deleted]
Skip Lists Done Right
11–20 of 87 posts
Re: Skip Lists Done Right
#12Something to note: you state that BST's have logarithmic time in order successor, but many implementations use threaded binary trees which provide an amortized constant successor operation. Great article though.
Re: Skip Lists Done Right
#13Redis uses a skip list (doubly linked) implementation for sorted sets, here are antirez's (BDFL) comments as to why from 7 years ago:
There are a few reasons:
1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
Re: Skip Lists Done Right
#14[Shameless plug] I've written a skip list implementation you can play with from the browser:
http://leandro.me/MyDataStructures/#/data-structures/skip-li...
Tip: click "Insert a random item" a bunch of times to populate the (initially empty) skip list.
Re: Skip Lists Done Right
#15Excellent article, I really love algorithm and datastructure. if anyone else is interested like me, I recommend this book https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...
It is also very handy if you need to flatten a small (< 2 kg) household pet.
On the upside, it is really cheap by weight.
Re: Skip Lists Done Right
#16> I can't seem to find my favorite trick: deterministic (ie. without rng) skipping by linking on traversal instead of insert/delete. Says one comment. Can anyone explain that?
I initially thought it might be referring to deterministic skip lists (Munro, Papadakis, Sedgewick, http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/det...), but the "linking on traversal" part stumps me. Maybe it's referring to the top-down approach in section 3 of the paper.
Re: Skip Lists Done Right
#17Looks like I already do pretty much all those things in twoskip: https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip... (except for the level choice. Which is a bit meh to me, because a write will probably trigger 3 fsyncs, so the cost of level choice is very low) That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk.
>That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk. What will you use instead (and why)?
B-trees, LSM trees, or any data structure that's actually designed to be cache friendly.
I think his claim that his optimizations can beat a b-tree is bullshit otherwise he would've shown benchmarks.
Re: Skip Lists Done Right
#18Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists.
Recently I got rid of huge bottleneck on an oldish piece of software by moving from a vanilla linked list to a skip list. And I did do many things suggested in the article (e.g. having a vector of fixed length for the pointers, and thus a fixed tallness).
Funnily enough, for my case, I managed to do without a RNG just fine. I just have an element that is of tallness 'k' every 2^(k*3) insertions (e.g. every 8th insertion is 1 level tall; every 64th insertion is 2 levels tall; and so on). For my particular pattern of insertions, this proved to be more than enough, and and simplified things a little bit.
Re: Skip Lists Done Right
#19> I can't seem to find my favorite trick: deterministic (ie. without rng) skipping by linking on traversal instead of insert/delete. Says one comment. Can anyone explain that?
It sounds like they mean that, if you have all the data you want for your skiplist and all you need going forward is a read-only data structure for doing lookups, then you can put your data in order in a regular list and then build up the towers of skip links in deterministic fashion to get an optimally balanced distribution.
Doesn't seem like much of a trick, though. If you can do that, then you can just stick it all in an array and bsearch to find things.
Re: Skip Lists Done Right
#20Another nice thing about skip lists is that you can traverse them backwards without adding backpointers with a recursive algorithm and an O[logn] size stack.