Redis 跳跃表

跳跃表是一种有序的数据结构，通过每个节点中维持多个指向其他节点的指针，提高节点的访问速度。跳跃表支持平均 O(logN) 的时间复杂度。

1 Redis跳跃表结构

2 zskiplist

1. header 跳跃表头节点。
2. tail 跳跃表的表尾节点。
3. level 层数最大的那个节点的层数。
4. length 跳跃表的长度，包含节点的数量。

typedef struct zskiplist {
    // 表头表尾节点
    struct skiplistNode *header, *tail;
    
    // 数量
    unsinged long length;
    
    // 层数
    int level;
}

3 zskipNode

1. level 节点各个层，每个层带有前进指针和跨度两个信息，每次创建一个新的跳跃表节点的时候，程序都会随机生成一个介于1-32之间的值作为level数组的大小。
2. 后退指针，当前节点的前一个节点。
3. 分值，在跳跃表中节点按照分值从小到大排列。
4. 成员对象。

对于表头节点只有层信息：

typedef struct zskiplistNode {
    // 层信息
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 前进跨度
        unsigned int span;
    } level[];
    
    // 后退指针
    struct zskiplistNode *backward;
    
    // 分值
    double score;
    
    // 成员对象
    obj *obj；
} zskiplistNode;

多个对象可以有相同的分值，但是不能有相同的成员对象。