Redis数据结构5：REDIS_SKIPLIST-摩杜云开发者社区

REDIS_SKIPLIST

skipList，即：跳表，或者叫跳跃表。skiplist的优势是能支持平均 O(logN) 复杂度的节点查找。

用一句话来说：skiplist就是一个有着索引的list。

编码结构

简单理解

简单来说，skipList有多层“索引”以加快查找速度：

其中L1、L2和L3都是一个list。

当查找8时，从L3查找到5，再从L2从5开始查找，查找到7，再L3中从7开始查找，最终查找到8。

这样，原本需要8次查找的操作直接简化到了4次。

从源码理解

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

Redis 只有 Zset 对象的底层实现用到了跳表。

Zset 需要你填入元素和权重，其中权重就是跳表用于排序的根源，即listNode中的score。

zskipList中的level即为跳表的层级， Zset的元素存储在listNode中的ele中，以sds形式存储。

SkipList的层级设计

前文提到，SkipList相邻两层的节点数量的比例会影响跳表的查询性能。

当设计不合理时，跳表的查询性能可能会降低到 O(n)。

**跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)**。

但Redis所提出的解决方案是：跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

skipList在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

// 创建一个空表头的跳表
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    // 尝试分配内存空间
    zsl = zmalloc(sizeof(*zsl));
    // 初始化level和length
    zsl->level = 1;
    zsl->length = 0;
    // 调用下面的方法zslCreateNode, 传入的参数有数组长度。
    // 分数0，对象值NuLL
    // 这一步就是创建管理所有节点的数组
    // 并且设置表头的头头指针为此对象的地址
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    // 为这32个数组赋值前指针forward和跨度span
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    // 设置尾指针
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    // 返回对象
    return zsl;
}

zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}

ZSKIPLIST_MAXLEVEL 定义的是最高的层数，Redis 7.0 定义为 32，Redis 5.0 定义为 64，Redis 3.0 定义为 32。

为什么要用跳表而不用平衡树？

对于这个问题，Redis作者@antirez如是回答：

There are a few reasons:

They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code. 简单来说：

1.Btree和SkipList不是内存密集型数据模型，用什么取决于你，只不过改变节点级数的时候SkipList可以比树用更少的内存。

2.Redis经常需要执行ZRANGE或ZREVRANGE命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。

3.SkipList实现简单，社区维护起来方便。比如社区提交来一个用O(logN)的ZRANK实现，只需要改动少量代码就能完成。

详细来说：

从内存占用上来比较，跳表比平衡树更灵活。平衡树每个Node固定包含 2 个指针（指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比树占用的内存更少。
在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对树进行改造，中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行遍历就可以实现。
从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单快速。