介绍

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同。

SkipList结构：

typedef struct zskiplist {
    //头尾节点指针
    struct zskiplistNode *header, *tail;
    //节点数量
    unsigned long length;
    //最大的索引层级，默认是1
    int level;
} zskiplist;

SkipListNode结构：

typedef struct zskiplistNode {
    sds ele； // 节点存储的值
    double score；// 节点分数，排序、查找用
    struct zskiplistNode *backward; // 前一个节点指针
    struct zskiplistlevel {
        struct zskiplistNode *forward; // 下一个节点指针
        unsigned long span； // 索引跨度
    } level[]；// 多级索引数组
} zskiplistNode;

特点

• 跳表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单