定义

跳跃表（skip list），简称跳表，是一个随机化的数据结构，实质是一种可以进行二分查找的有序链表。跳跃表在原有的单向有序链表上增加了多级的索引，通过索引实现快速查找，快速插入，快速删除的性能。

跳跃表可以看作是二叉树的一个变种，在性能上与红黑树，AVL树等不相上下，但是实现原理相对简单很多，目前在redis和levelDB中均有使用。

实现原理

对于一个单向的有序链表而言，如果我们想在链表中查找某个数据，只能从头到尾遍历链表，这样的查找效率比较低，时间复杂度也会很高，复杂度为O(n)。

单链表.png

为了提高查找的效率，我们可以考虑在单向有序链表上增加索引的方式，比如，每两个链表结点提取一个结点到上一级，我们将抽出来的那一级别叫做索引，如下图：

一层跳跃表.png

假设我们需要查找结点8，可以先在索引层（L1）进行遍历，当遍历到索引层中值为7的结点时，发现下一个结点的值为9，那么，需要查找值为8的结点必然在这两个结点之间，这时我们可以下降到链表层继续遍历，就可以找到了值为8的结点。

原先我们在单向有序链表中查找值为8的结点，需要遍历8个结点才能查找到，而增加了一级索引的跳跃表中，只需要遍历5个结点就能查找到，查找性能得到提升。

理论上，如果我们再增加一层索引，则查找效率可以得到进一步的提升：

二层跳跃表.png

在以上的例子中，结点数量较少，当结点数量较大时，可以进一步增加多级索引，其查找效率可以得到明显的提升。比如下图表示的三级索引：

跳跃表.JPG

redis中跳跃表的使用

在redis中使用跳跃表作为有序集合的底层实现之一，如果一个有序集合中包含的元素的数量比较多时，或者有序集合中元素的成员比较长时，redis就会使用跳跃表作为有序集合的底层实现。

跳跃表在单向有序链表的基础上，增加了多级索引以提升查找的效率，这本质上是一个空间换时间的解决方案，索引是占用内存的。在原始的单向有序链表中存储的值有可能是很大的对象，而索引结点值需要存储关键值和相关的几个指针，并不存储值对象，因此当结点本身比较大时，或者元素数量比较多时，跳跃表的优势就会被放大，而缺点可以忽略，这就是redis在特定情形下使用跳跃表的原因。

在redis中，跳跃表是由redis.h/zskiplistNode和redis.h/zskiplist这两个结构体定义的。其中zskiplistNode表示跳跃表的结点，而zskiplist表示跳跃表的相关信息，比如结点数量，执行表头与表尾的指针等。

redis_一个跳跃表.png

上图展示了一个跳跃表的示例。图中展示的是最左边的zskiplist结构，以及四个zskiplistNode结点。

zskiplist结构包含的属性主要包括：

• header：指向跳跃表的表头结点
• tail：指向跳跃表的表尾结点
• level：记录当前跳跃表中，层数最大的那个结点的层数（不包括表头节点的层数）
• length：记录跳跃表的长度，即跳跃表中包含的结点的数量（不包括表头结点）

zskiplistNode结构包含的属性主要包括：

• level：层，结点中使用L1、L2、L3等字样标识结点中的各个层，每个层都带有两个属性，即前进指针与跨度。前进指针用于访问位于表尾方向的其他结点，而跨度记录了前进指针所指向的结点和当前结点的距离。在上图中，连线上带有数字的箭头代表了前进指针，数字就是跨度
• backward：后退指针，在上图中各个结点使用BW来标识，执行位于当前结点的前一个结点，后退指针可以在程序从表尾向表头遍历时使用
• score：各个结点中对象的分值，在跳跃表中，结点按照各自所保存的分值从小到大排序，redis有序集合使用分值作为集合元素排序的依据
• obj：成员对象，即结点中保存的成员对象

在redis源码中，上述结构的定义源码为：

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


/**
 * 跳跃表结构体
 */
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

/**
 * 有序集合结构体
 */
typedef struct zset {
    /*
     * Redis 会将跳跃表中所有的元素和分值组成 
     * key-value 的形式保存在字典中
     * todo：注意：该字典并不是 Redis DB 中的字典，只属于有序集合
     */
    dict *dict;
    /*
     * 底层指向的跳跃表的指针
     */
    zskiplist *zsl;
} zset;