1. 跳跃表的用处

1. 有序集合(zset)的底层可以采用数组, 链表, 平衡树等结果来实现, 但是他们都有各自的缺点 . 数组方便查询, 但不便于插入和删除, 链表方便插入和删除, 但是不利于查找, 平衡树/红黑树效率高但是实现起来很复杂
2. 所以Redis自己实现了跳跃表来来当做有序集合(zset)的底层实现, 他的查询复杂度平均O(logN), 最坏O(N), 堪比红黑树, 但实现起来远比红黑树简单

2. 跳跃表的具体示例

我们先来看一下如果用有序链表来实现有序集合

插入和删除为O(1), 但是查找的复杂度为O(N)
但是我们看跳跃表的实现

我们从有序链表中选取部分节点, 组成一个新的链表如图中的10 -> 30 -> 50 -> 70 -> null, 当做一级索引
如果一级索引中节点还是很多, 我们可以再从一级索引中选取部分节点, 再组成一个新的链表, 并以此作为原始链表的二级索引10 -> 50 -> null

跳跃表的查找

那么跳跃表是如何进行查找的呢

1. 优先从高层查找
2. 若当前节点的值, 小于要查找的值, 并且next指针指向大于目标值的节点, 就要降一级寻找, 或者next指针指向了null, 那么也需要降一级查找

跳跃表的具体实现

跳跃表底层使用了zskiplist, 和zskiplistnode两个结构体来实现
zskiplist

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

• header 指向跳跃表表头节点, tail指向表尾节点
• length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)
• level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)，通过这个属性可以在O(1)的时间复杂度内获取层数最高的节点的层数。

typedef struct zskiplistNode {
    sds ele;
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        /**
         * 跨度实际上是用来计算元素排名(rank)的，
         * 在查找某个节点的过程中，将沿途访过的所有层的跨度累积起来，
         * 得到的结果就是目标节点在跳跃表中的排位
         */
        unsigned long span;
    } level[];
} zskiplistNode;

• backward 指针指向前一个节点, 用于方便寻找数据

• sds动态字符串存储内容, score存储分数, 用来排序使用

• level(每个节点的层数) :
  节点中用1、2、L3等字样标记节点的各个层,L1代表第一层,L代表第二层,以此类推.

  每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。
  

相当于这是三个节点第一个节点处于第0层, 第二个节点他是可以处于三层, 第三个节点可以处于5层

下图是根据具体一点的一个跳跃表实现

header指向的是一个层高为32的伪头结点, 实际链表的开端是这个伪头结点的后一个节点, 根据这个伪头结点就可以快速的找到层数最高的, 因为其他节点的层数都是要比32小的

本文重点

• 跳跃表基于单链表加索引的方式实现
• 跳跃表以空间换时间的方式提升了查找速度
• Redis有序集合在节点元素较大或者元素数量较多时使用跳跃表实现
• Redis的跳跃表实现由 zskiplist和 zskiplistnode两个结构组成,其中 zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistnode则用于表示跳跃表节点
• Redis每个跳跃表节点的层高都是1至32之间的随机数