redis中的跳跃表

Redis已经越来越多的被应用。本文主要讨论的是跳跃表(skiplist)在redis中的应用。

跳跃表

跳跃表(skiplist)是一种随机的数据结构，以有序的方式在链表中保存数据，可以达到和平衡树类似的效率，增删改查可以在对数复杂度时间内完成。

跳跃表示例

从上图看出，跳跃由以下几个部分组成：

• 表头（head）：负责维护跳跃表的节点指针。 
• 跳跃表节点：保存着元素值，以及多个层。 
• 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。 
• 表尾：全部由 NULL 组成，表示跳跃表的末尾。

Redis中的跳跃表

为了满足自身的要求，redis在使用跳跃表时做了以下改动： 

1. 允许重复的 score 值：多个不同的 member 的 score 值可以相同。 
2. 进行对比操作时，不仅要检查 score 值，还要检查 member ：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。 
3. 每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代。当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。

以下是操作这两个数据结构的 API ，API 的用途与相应的算法复杂度：

函数	作用	复杂度
zslCreateNode	创建并返回一个新的跳跃表节点	最坏 O(1)
zslFreeNode	释放给定的跳跃表节点	最坏 O(1)
zslCreate	创建并初始化一个新的跳跃表	最坏 O(1)
zslFree	释放给定的跳跃表	最坏 O(N)
zslInsert	将一个包含给定 score 和 member 的新节点添加到跳跃表中	最坏 O(N) 平均 O(logN)
zslDeleteNode	删除给定的跳跃表节点	最坏 O(N)
zslDelete	删除匹配给定 member 和 score 的元素	最坏 O(N) 平均 O(logN)
zslFirstInRange	找到跳跃表中第一个符合给定范围的元素	最坏 O(N) 平均 O(logN)
zslLastInRange	找到跳跃表中最后一个符合给定范围的元素	最坏 O(N) 平均 O(logN)
zslDeleteRangeByScore	删除 score 值在给定范围内的所有节点	最坏 O(N2)
zslDeleteRangeByRank	删除给定排序范围内的所有节点	最坏 O(N2)
zslGetRank	返回目标元素在有序集中的排位	最坏 O(N) 平均 O(logN)
zslGetElementByRank	根据给定排位，返回该排位上的元素节点	最坏 O(N) 平均 O(logN)

参考资料

• http://redisbook.readthedocs.org/en/latest/internal-datastruct/skiplist.html
• http://en.wikipedia.org/wiki/Skip_list