Redis 数据结构之跳跃表

跳跃表是一种有序数据结构，它通过每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的

跳跃表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点

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

除了有序集合，跳跃表在 Redis 的另一个用途是在集群节点中用作内部数据结构

跳跃表实现

位于图片最左边的是 zskiplist 结构，用于保存跳跃表信息

通过两个指针，程序定位表头节点和表尾节点复杂度都为 O(1)
通过 length 属性，程序可以在 O(1) 时间内返回跳跃表的长度

右方是四个 zskiplistNode 结构，用于表示跳跃表节点

每个跳跃表节点层高都是 1 至 32 之间的随机数

在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的

跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的字典序进行排序