跳跃表 (SkipList) 是对链表 (LinkedList) 结构的延伸, 在单链表中, 除最后一个结点外, 每个结点都有 Next 指针指向它的后继结点, 对于双向链表, 除首尾结点之外, 每个结点都有 Previous 和 Next 指针分别指向它的前驱和后继结点, 无论是单链表还是双向链表, 结点之间的关联关系都只存在于相邻结点之间, 而对于跳跃表来说, 每个结点有多个指针, 除了指向它的相邻结点之外还设置指向其它非相邻结点的指针, Redis 在底层使用跳跃表来作为 zset 键的一种实现方式, 本文讨论跳跃表的结构以及 Redis 对跳跃表的实现

27.1 跳跃表 (SkipList) 的结构

跳跃表的每个结点有多个指针, 同时每个指针有一个跨度属性, 跨度指示该指针指向的结点与当前结点的距离, 同时每个结点也有一个前向指针指向前一个相邻的结点便于倒序遍历, 双向链表可以看做是跳跃表的一种特殊情况, 它的每个结点只有一个指针, 并且指针的跨度都是 1, 对此进行扩展便得到了跳跃表

27.2 Redis SkipList 结构

Redis 关于跳跃表的结构定义位于 src/redis.h 中, 它的结点结构如下所示:

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

其中 obj 指向结点存放的对象, score 为该元素的分数, Redis 跳跃表的结点按照 score 大小进行排序, backward 为后向指针, 指向跳跃表的前一个结点, zskiplistLevel 是一个结构体数组, 它的每一个元素由指针和跨度构成, 跨度指示指针指向的结点与当前结点的逻辑距离

Redis 跳跃表的定义如下所示:

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

zskiplist 中分别含有跳跃表的头指针和尾指针, 同时还有跳跃表的长度 (即跳跃表结点的数量) 以及跳跃表中所有结点的最大层数, Redis 在创建跳跃表结点时随机在 1 ~ 32 之间选取一个数值作为结点的层数 (即包含指针的数量), 第一层指针的跨度为 1, 指向跟随其后的相邻结点, 第二层指针的跨度为 2, 指向其后继结点的后继结点, 以此类推, 第 N 层指针的跨度为 N, 在应用上, 跳跃表的跨度可以用于实现 ZANK KEY MEMBER 指令, 将遍历过程中的跨度累积起来便是 MEMBER 的 RANK 结果