Redis-跳跃表(skiplist)

什么是跳跃表？看笔记”跳跃表(skiplist) “,本文主要介绍跳跃表在 Redis 的应用、核心数据结构和 API 。

用途

说真的，跳跃表在 Redis 中使用不是特别广泛，只用在了两个地方。

作为有序集合键实现之一（如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员(member)是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。）
集群节点中用作内部数据结构。

数据结构

- 这样的结构，获取表头、表尾节点，表长，以及表中最高层数的复杂度均为O(1)。 - 位于图片最左边的是zskiplist结构，由 redis.h/zskiplist 定义： ``` C typedef struct zskiplist {

// 头节点，尾节点（指向跳跃表的表头节点，表尾节点）
struct zskiplistNode *header, *tail;

// 节点数量-记录跳跃表的长度，也即是跳跃表目前包含节点的数量（表头节点不计算在内）
unsigned long length;

// 目前表内节点的最大层数-记录目前跳跃表内，层数最大的那个节点的层数(表头节点的层数不计算在内)
int level;

} zskiplist;

因此, `redis 的跳跃表底层为双向链表，并持有尾指针方便从尾遍历`

- 位于zskiplist结构右方的是四个zskiplistNode结构，
由 redis.h/zskiplistNode 定义：
``` C
typedef struct zskiplistNode {

    // member 对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 这个层跨越的节点数量
        unsigned int span;

    } level[];

} zskiplistNode;