What is a skip list?
In short, skip lists are a linked-list-like structure which allows for fast search. It consists of a base list holding the elements, together with a tower of lists maintaining a linked hierarchy of subsequence, each skipping over fewer elements.
Skip list is a wonderful data structure, one of my personal favourites, but a trend in the past ten years has made them more and more uncommon as a single-threaded in-memory structure.
My take is that this is because of how hard they are to get right. The simplicity can easily fool you into being too relaxed with respect to performance, and while they are simple, it is important to pay attention to the details.
In the past five years, people have become increasingly sceptical of skip lists’ performance, due to their poor cache behaviour when compared to e.g. B-trees, but fear not, a good implementation of skip lists can easily outperform B-trees while being implementable in only a couple of hundred lines.
How? We will walk through a variety of techniques that can be used to achieve this speed-up. Continue reading →