跳表

skiplist

跳表

• 跳表是 Redis 数据库 Zset 对象的底层实现，优势是能支持平均 $O(\log n)$ 复杂度的节点查找

• 跳表的基础是一个有序链表，最底层包含所有节点。

• 在此基础上，增加多层索引层。每一层都是上一层的“稀疏版本”，也就是说，只有部分节点会被随机提升到更高的层。

• 例如，最底层可能是 [1, 2, 3, 4, 5]，而第一层索引可能是 [2, 3, 5]，第二层可能是 [3,]。

算法

假设为升序，以 Zset 的跳表实现为例：

数据结构

typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

跳表节点结构包含了

• 值
• 权重
• 后向指针
• Level 数组：每一个元素代表跳表的一层
  • zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」，跨度用来记录两个节点之间的距离。

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

跳表结构里包含了：

• 跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
• 跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量；
• 跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量；

Ref: xiaolincoding, leetcode 1206