跳跃表是一种有序数据结构,它通过每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的
跳跃表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找,还可以通过顺序性操作来批量处理节点
如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时,Redis 就会使用跳跃表来作为有序集合键的底层实现
除了有序集合,跳跃表在 Redis 的另一个用途是在集群节点中用作内部数据结构
跳跃表实现
位于图片最左边的是 zskiplist 结构,用于保存跳跃表信息
通过两个指针,程序定位表头节点和表尾节点复杂度都为 O(1)
通过 length 属性,程序可以在 O(1) 时间内返回跳跃表的长度
右方是四个 zskiplistNode 结构,用于表示跳跃表节点
每个跳跃表节点层高都是 1 至 32 之间的随机数
在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的
跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的字典序进行排序