Redis源码阅读(八) – skip list

Redis内的有序集合zset使用skip list保存scoreobject的映射,同时按照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为该结点的levellevel=n+1的结点数量是level=n的结点数量的1/p,这个由随机level生成算法决定,Redis内部为1/4

image

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

分类:

更新时间: