Skip Lists: A Probabilistic Alternative to Balanced Trees
en.wikipedia.org
en.wikipedia.org
There are several negatives, however. One is that skiplists use about (lg n)/2 times as many pointers as a balanced tree, if you actually make your skiplist tall enough to be worthwhile. This could mean an extra MB or more of memory for a skiplist with 100K items in it. In some cases it could be that half of the memory consumed by the skiplist is the overhead involved in creating the skiplist. This is also true of hash tables that don't have many elements, of course, but with hash tables, the situation gets better as more items are added. With skiplists, the overhead remains high regardless of the number of items in the list.
Another "problem" is that of standard libraries. Even C has a tsearch function (in search.h) that implements balanced search trees, and many other languages include balanced search trees as well. Balanced search trees have less overhead, both in terms of memory and performance. With a skiplist, you have to choose a few random numbers (on average) for every item added to the tree. Then with searches, you always have to start at the top (the "skippiest" part) with comparisons, working your way down towards the bottom until you figure out which node to jump to. With BSTs, it's just a single comparison and then a movement left or right.
And of course, if your items are hashable, skiplists really lose out to hash tables, which have near-constant lookup time, very little overhead as the number of items in your table approaches the capacity, and implementations in nearly every language.
This post summarizes several potential problems with hash tables: http://enfranchisedmind.com/blog/2008/02/25/problems-with-ha...
In particular, the hashing approach gives similar lookup times for any item. The skiplist approach is dependent on the (random) structure of the built-up skiplist. A given item could be found after 2 pointer traversals, or it could take 30. Also disturbing is that as you get closer to the item you're looking for, the string comparisons take longer and longer (because the common prefixes are getting longer and longer).
With a good hashing algorithm, similar strings will hash to different values. This means that even if 2 or 3 string comparisons have to be made (for strings that land in the same bucket), failing comparisons will be fast since they will likely fail on the first character.
Also, good point about string comparisons getting longer among close nodes.
Personally, I think skiplists are most interesting because they rely on randomness to make the underlying structure efficient. I wonder what over data structures that could apply to.
In other words the memory usage is not really an issue with skiplists.
I may have to revisit my implementation and do it "right".
(It's true that balanced trees take a little more than two pointer per node, but e.g. red-black trees only need one extra bit, which you can pack into the bottom of one of the pointers if you like).
On the whole, skip lists are cute, but not really "better" than a red-black or AVL tree. And the balanced trees aren't that hard to implement, even if you decide to do your own. Add that to the fact that tree stuctures in code are kinda esoteric (almost always, you just want to be able to fetch an item by identity. Range comparisons are pretty rare in memory -- that's what databases are for) and skip lists leave me a little ... meh.
In my comment, I was referring to my (and the reference) implementation. After reading your comment, though, you're right that you could allocate a number of pointers equal to the height of the specific node. The only downside is that you then have two mallocs for each new node (once for the node and once for its array of pointers), unless you do something hackish like putting the array of pointers at the end of the struct and manually adjusting your malloc call to allocate the right amount.
One other note: I don't think my skiplist was doubly-linked. The search algorithm involves moving forward on the highest level until the move would take you past the desired element, then you move down a level and continue. By the time you hit the bottom, you're guaranteed to either hit the element you're looking for, or your position is the node before where the element would be if it was in the list. Thus double-linking is entirely unnecessary.
If I remember right, skip lists are unfriendly to caches (compared to balanced search trees) because they don't optimize locality of reference. This matters, for example, when your huge dataset is on disk and you're trying to cache the working set in memory. In a skip list, related elements don't end up on the same page as often, which means you have to read more data than you need from disk, and read from the disk more often.
By all means stick to caching/LRU/B*tree if that works for your application. A cache is a brute-force solution, tho', and it helps to have more than one tool in your bag.
Skiplists end up with a ton of pointer chasing and hence dramatically increase the pressure on the memory cache. There's no real, profitable way around that fact.
You might want to look at the non-block hashtable work that I pointed to previously for a lot of information (and the actual code (in Java) is up on SF.net so you can actually try it out for yourself).