Redis之跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持毒功而指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O(logN)，最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

跳跃表的使用场景

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

跳跃表的定义

// server.h
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    // 必须唯一，分值相同时按照ele的字典序排列
    sds ele;
    // 分值，所有节点按分值从小到大排序
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        // 跨度，用于计算该节点在跳跃表中的序号
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    // 跳跃表的长度（不包含表头节点）
    unsigned long length;
    // 层数最大的节点的层数（不包含表头节点）
    int level;
} zskiplist;

zskiplistNode.score：节点的分值，节点在跳跃表中按照分值从小到大排列。

zskiplistNode.ele：节点保存的数据对象，节点的分值相同时，根据ele的字典序排序。

zskiplistNode.level：节点的层数组，程序通过这些层来加快访问其他节点的速度。每次创建新节点时回根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的高度。

跳跃表的结构图

跳跃表.PNG