第5章 跳跃表

https://www.jianshu.com/p/9d8296562806

跳跃表(skiplist)是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的. 跳跃表支持平均O(logN), 最坏O(N)的节点查找复杂度, 效率可以与平衡树媲美, 而且实现比平衡树简单; 还可以使用顺序性操作来批量处理节点.

Redis使用跳跃表作为有序集合键的底层实现之一. 如果一个有序集合包含的元素数量比较多, 或者元素的成员是比较常的字符串时, 就会使用跳跃表.

除此之外, 跳跃表只被用在集群节点中作为内部数据结构.

5.1 跳跃表的实现

typedef struct zskiplist {
 // 表头节点和表尾节点
 struct skiplistNode *header, *tail;
 // 节点的数量
 unsigned long length;
 // 层数最大的节点的层数
 int level;
} zskiplist;

• 每次创建一个新跳跃表节点时, 程序都根据幂次定律随机生成一个介于1到32之间的值作为level数组的大小, 即节点的索引级别.

  • 每层都有一个指向表尾方向的前进指针forward, 用于向表尾方向访问节点

  • 层的跨度span用于记录两个节点之间的距离. 跨度与遍历无关, 而是用于计算rank, 在查找过程中的跨度之和就是节点的rank

• 节点的后退指针backward每次只能后退至前一个节点, (用于增删改节点时更新前置节点的span???)

• 节点还包含一个分值score和一个对象obj指针, obj中则保存一个SDS值. 节点保存的成员对象必须唯一, 但是分值允许相同, 节点间先比较分值, 分值相同再比较对象的字典序, 从小到大排序.

5.2 跳跃表API