引言：跳跃表是一种有序数据结构，它通过在每个节点中维持多个执行其他节点的指针，从而达到快速访问节点的目的。跳跃表的查询速度可以和平衡书相媲美，平均时间复杂度O(logN)，最坏O(N)，但实现起来比平衡树要简单很多。

跳跃在redis中只有两个地方使用，一个是有序集合（zset还使用了字典加跳跃表实现），另一个是集群节点中用作内部数据结构。

一、实现

跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构体实现

1.1、跳跃表节点

struct zskiplistNode{

    struct zskiplistNode *backward;// 后退指针

    double score;// 分值

    robj *obj;// 成员对象

    struct zskiplistLevel { // 层；

         struct zskiplistNode *forward; //前进指针

        unsigned int span; //跨度

    } leve[];

}

level: 该数组可以包含多个元素，每个元素都包含一个前进指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层数越多，节点访问速度越快。

forward:用于从表头向表尾方向访问节点

span:跨度，用于记录两个节点之间的距离。跨度实际上是用于排位的，在查找某个节点的时候，将沿途访问过的所有层的跨度全部加起来，就是目标节点在跳跃表中的排位。

barkward:用于从表尾向表头方向访问节点

score和obj：score是浮点数，用来排序。obj是一个指针，指向的是字符串对象，注意：一定是字符串对象，这个字符串对象保存的是SDS值，也就是说跳跃表的值是SDS。其中，obj一定是唯一的，但是分值可以相同。如果分值相同，就按照字典顺序排序，升序。

1.2、跳跃表

struct zskilist{

    struct skiplistNode *header *tail; //表头和表尾节点

    unsigned long length;// 节点数量

    int level;// 表中层数最大的节点的层数

}

二、注意点

跳跃表的值robj一定是个字符串对象，说明redis的跳跃表只能保存字符串，zset也只能保存字符串，这个值必须是唯一的。score可以相同。

三、番外

golang实现跳跃表：https://www.jianshu.com/p/400d24e9daa0?from=timeline&isappinstalled=0

有疑问加站长微信联系（非本文作者）