跳跃表

https://mp.weixin.qq.com/s/NOsXdrMrWwq4NTm180a6vw

跳跃表的set 保证了内部 value 的唯一性，同时又可以给每个 value 赋予一个排序的权重值 score，来达到 排序的目的。

节点

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度：记录两个节点之间的距离，计算排名rank
        unsigned int span;
    } level[];
} zskiplistNode;

查找

跳跃表基于多层链表。上面每一层链表的节点个数，是下面一层的节点个数的一半。类似于一个二分查找，时间复杂度 O(logn)。

插入

为节点随机出一个层数，只需要修改节点前后的指针，而不需要对多个节点都进行调整

随机：50% 的概率被分配到 Level 1，25% 的概率被分配到 Level 2，12.5% 的概率被分配到 Level 3……

1. 找到当前我需要插入的位置 （相同 score 时比较 value）
2. 用临时数组保存每一层的后继指针
3. 创建新节点，调整前后的指针指向

对比树结构的优势

1. 树范围查找时需要中序遍历
2. 插入删除会导致树结构调整
3. 占用空间

应用：排行榜

• 以当前小时的时间戳作为 zset 的 key
• 把贴子ID作为一个value值，与score关联
• 点击数评论数等作为 score，当 score 发生变化时更新 score