Redis源码阅读(八) – skip list

Redis内的有序集合zset使用skip list保存score到object的映射，同时按照score排序。skip list是由William Pugh提出的，Redis的实现 也是参考了他的论文Skip Lists: A Probabilistic Alternative to Balanced Trees:

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

skip list具有随机性，它的查找、插入和删除的摊还时间复杂度为O(lgn)。skip list分为多个level，最底层就是普通的链表。结点的最高level为该结点的level， level=n+1的结点数量是level=n的结点数量的1/p，这个由随机level生成算法决定，Redis内部为1/4。

从上图可以看到，按照level从高到低查找，只需要O(lgn)次即可找到目标。skip list相比于红黑树等平衡树的一个很大优势是实现简单，更容易实现lock free的结构。 具体的算法和复杂度分析都在论文里。