跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的
Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，redis就用跳跃表来作为有序集合键的底层实现。

5.1 跳跃表的实现

• zskiplistNode 用于表示跳跃表节点

• zskiplist 用于保存跳跃表节点的相关信息

  
  

• header 指向跳跃表的表头节点

• tail 指向跳跃表的表尾节点

• level 记录目前跳跃表内，层数最大的节点的层数

• length 记录跳跃表的长度

• 层（level） 节点中用L1、L2等表示节点的每个层

• 后退（backward） 节点中用BW表示的后退指针，用于从后往前遍历

• 分值（score） 每个节点的分值，决定节点的排序

• 成员对象（obj） 各个节点中 o1、o2即是成员对象

5.1.1 跳跃表节点（zskiplistNode）

1、层

• level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，数组越大，访问其他节点就越快
• 每次创建一个新跳跃表节点的时候，程序都根据幂次定律随机生成一个1-32的值作为数据大小，即层“高”

2、前进指针

• 从表头开始，每个前置都有指向后面节点的指针，称为前进指针

3、跨度

• 记录节点之间的距离
• 指向NULL的指针跨度为0

4、后退指针

• 用于从表尾指向表头
• 每个节点只有一个后退指针，指向前一个节点

5、分值和成员

• 分值为double类型浮点数，节点按分值从小到大排列

• 节点的成员对象（obj）是一个指针，指向一个字符串对象，而字符串对象则保存着一个SDS值。

  
  

5.1.2 跳跃表（zskiplist）

快速获得表头（head）表尾（tail）节点数量（length）和最高层数（level，不包含表头结点）

5.2 跳跃表API

跳跃表API

5.3 重点回顾

以上

欢迎大家关注我的公众号

半亩房顶