Redis 跳跃表（skiplist）

1. 跳跃表的原理

• 传统有序链表查询节点需要遍历，复杂度为O(n)。

  
  《Redis5设计语言与源码分析》
• 上图可理解为三层有序链表，每列都代表相同的元素值，当做冗余。
• 以上图为例当查询节点51时，开始从顶层左侧开始遍历，链表下个节点为21，小于结果51，则继续查询，后续为null，则向下移，到第一层21位置，判断下个节点，41继续判断下个，61大于51则下移到第0层41位置，再下个节点为就是51。
• 这种跳表方式比线性存遍历少了2次查询，元素数量多时更有效率。

2. 跳跃表结构

《Redis5设计语言与源码分析》

• 图中最左边红框的是zskiplist辅助作用，右边每列都是一个zskiplistNode节点（重点），zskiplist header指向头结点，头结点高度默认64，初始化时默认生成，不代表具体数据。
• zskiplistNode结构：

typedef struct zskiplistNode {
    sds ele;  // 对应zset的字符串数据
    double score;   // 对应zset里的分值
    struct zskiplistNode *backward;  // 指向前一个节点
    // 用柔性数组代表图上列的高度
    struct zskiplistLevel {
        struct zskiplistNode *forward;  //指向本层的下个节点
        unsigned long span;  // 本层的下个节点跨了几个元素
    } level[];
} zskiplistNode;

• zskiplist结构：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;   // 如图代表头结点、尾节点
    unsigned long length;  //表长
    int level;  // 表高
} zskiplist;

3. 跳跃表实现

• 创建：
  • 确定节点高度：每个节点的高度是0~63里随机的，高度越高概率越低，初始化为1层，每次取随机数有25%的几率再加一层继续循环，直到没有命中就跳出，最终确定层数，所以层数高的几率还是比较小的。
  • 上面说过初始化时就默认带头结点，所以需要初始化一个高度64的节点，分值为0，因为没有后续节点所以zskiplistLevel的forward都是null。
• 添加和删除操作没有太难理解的，维护跳跃表forward、backward等相关数据和表结构即可。

4. 跳跃表应用

• Redis中主要用于有序集合，是有序集合的一种实现方式，有两个相关配置，满足一条就会转化成跳跃表，根据结构可以得知跳跃表是空间换效率的方式，所以阈值过低会导致内存浪费。
  • zset-max-ziplist-entries(128)：zset元素个数大于128时转化为跳跃表，否则是ziplist。
  • zset-max-ziplist-value(64)：zset有元素长度大于64时转化为跳跃表，否则是ziplist。