Aren't skip lists more-or-less essential for indexed search engines? I wouldn't say they're uncommon considering how much indexed search surrounds us.
e.g., http://lucene.apache.org/core/6_3_0/core/org/apache/lucene/c...
Skip Lists Done Right
21–30 of 87 posts
Re: Skip Lists Done Right
#22Redis 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 o…
Data structures in Redis have evolved a bit in the last 7 years. One of the main workhorses is indeed something called a "ziplist". The implementation (especially the format description at the top) is worth a read: https://github.com/antirez/redis/blob/90a6f7fc98df849a9890ab...
For those who are familiar with pre-2.6 Redis code, there used to be something called zipmap, but it was deprecated in favor of ziplist.
Re: Skip Lists Done Right
#23Excellent 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.
It would be bad to have a book about multiple trees which implemented less than 1 tree in its printed form.
Re: Skip Lists Done Right
#24Skip 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…
> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists.
I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is the premise of the linked article, after all).
Using a skip list is frequently the better choice for performance and memory reasons (especially if you're iterating through the list), but they are not necessarily simpler data structures.
Re: Skip Lists Done Right
#25Redis 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 o…
Data structures in Redis have evolved a bit in the last 7 years. One of the main workhorses is indeed something called a "ziplist". The implementation (especially the format description at the top) is worth a read: https://github.com/antirez/redis/blob/90a6f7fc98df849a9890ab... For those who are familiar with pre-2.6 Redis code, there used to be something called zipmap, but it was deprecated in favor of ziplist.
I have not looked at Redis code in eons, but I think it's not exactly true - all the structures are there, it's just that redis will favor ziplist for the very small ones.
A ziplist is a list of compact varying length integers (or strings) where only the bits that make a difference are stored (I contributed the 24-bit version to Redis[1]). The argument is that a sequential search over a small data structure always wins over more complex things like hash tables, skiplists, etc.
As you get more data, Redis will switch to using skiplists or whatever - there is a config setting for that (-max-ziplist-entries and -max-ziplist-value).
[1] https://github.com/antirez/redis/commit/5a86ab47995586f0a0ef...
Re: Skip Lists Done Right
#26Excellent 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.
I always say college was very practical learning as at different points in time I was able to kill a mouse with both algorithms (this very book) and computer architecture.
Re: Skip Lists Done Right
#27Most interesting aspect of the article was the last section and first comment, linking to SkipNet: http://research.microsoft.com/en-us/um/people/alecw/usits-20...
Ideas like SkipNet are what differentiates a hack like me from genuinely smart people who can look at the definition of in-memory data structure and spot properties useful to an Internet-sized system
Re: Skip Lists Done Right
#28The author states in the "Extra Remarks" section:
"Performance is mostly about the same, but skip lists are more DoS resistant if you make sure that all links are F2F."
Can someone tell me what F2F stands for? I am not familiar with this acronym.
Re: Skip Lists Done Right
#29The author states in the "Extra Remarks" section: "Performance is mostly about the same, but skip lists are more DoS resistant if you make sure that all links are F2F." Can someone tell me what F2F stands for? I am not familiar with this acronym.
My guess is friend-to-friend, i.e. a private peer-to-peer network.
Re: Skip Lists Done Right
#30MemSQL (distributed relational database with in-memory tables) uses skip lists: http://blog.memsql.com/the-story-behind-memsqls-skiplist-ind...