Redis数据结构-SkipList {#redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-skiplist}

在《Redis数据结构》中我们说到Redis的Soted Set 类型底层使用的是ziplist以及skiplist，然后在Redis7.0的时候正式使用listpack替换了ziplist，本文主要简单说下skiplist，观关于ziplist以及listpack可以看看《Redis数据结构-ZipList与ListPack》这篇文章。

什么时候使用skiplist {#%E4%BB%80%E4%B9%88%E6%97%B6%E5%80%99%E4%BD%BF%E7%94%A8skiplist}

在Redis中只有Sorted Set 使用到了skiplist。skiplist在查找、删除、添加等操作的时间复杂度都是O(log~2~N)，这就是跳跃表的优点，其缺点就是需要的存储空间比较大，属于用空间换时间的类型。

在Redis的配置文件中我们可以看到这么两个配置：

# 与Hash以及List类型类似，为了节省大量空间，
# Sorted Set在存储时也会被特殊编码。这种编码仅在Sorted Set的长度和元素低于以下限制时使用：
# ==============================Redis6.0==============================
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
# ==============================Redis7.0==============================
zset-max-listpack-entries 128
zset-max-listpack-value 64

这里使用Redis7.0来测试，首先将配置zset-max-listpack-entries改小一点方便测试，这里我们改成3：

127.0.0.1:6379> CONFIG SET zset-max-listpack-entries 3
OK
127.0.0.1:6379> ZADD zset1 1 a 2 b 3 c
(integer) 3
127.0.0.1:6379> OBJECT ENCODING zset1
"listpack"
127.0.0.1:6379> ZADD zset1 4 d
(integer) 1
127.0.0.1:6379> OBJECT ENCODING zset1
"skiplist"

可以看到这里元素数量超过3后，编码方式就从listpack变成了skiplist，然后我们再将配置zset-max-listpack-value改成5：

127.0.0.1:6379> CONFIG SET zset-max-listpack-value 5
OK
127.0.0.1:6379> ZADD zset2 1 a
(integer) 1
127.0.0.1:6379> OBJECT ENCODING zset2
"listpack"
127.0.0.1:6379> ZADD zset2 1 abcdefg
(integer) 1
127.0.0.1:6379> OBJECT ENCODING zset2
"skiplist"

同理当我们添加的元素长度超过5后，编码方式也会从从listpack变成了skiplist。

skiplist是什么 {#skiplist%E6%98%AF%E4%BB%80%E4%B9%88}

单向链表 {#%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8}

首先我们先来看一个单向链表，即使这个链表中的数据都是有序的，但是当我们想要查找某一个数据的时候，也只能遍历这个链表，时间复杂度是O(n)，比如在下面这个链表中，想要查找39，则需要遍历8次才行。

单向链表

我们都知道数组以及链表它们都有自己的优缺点，那有没有办法搞一种数据结构，使得链表的遍历也能快呢？

既然链表遍历慢，时间复杂度是O(n)，那尝试给链表加个索引是否能变快呢？这里将上面的链表稍微改造一下，我们在每个节点上新增一个指针down，并且垂直扩充链表，最后可以得到下面这样一个数据结构：

增加多级索引的单向链表

这样就相当于增加一个"捷径"（多级索引），减少了遍历的次数，这个时候我们仅仅只需要查找2次就可以查找到39，但是相对的维护这么一个结构也增加了内存空间的消耗。

skiplist {#skiplist}

从上面我们就可以得知，skiplist实际就是一个用空间换时间的数据结构，skiplist提取出链表中的关键节点（索引），先在关键节点上面查找，再进入下层链表查找，这样提取出多层的关键节点，最后就形成了跳跃表（skiplist）。

时间复杂度 {#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6}

如果一个链表有N 个节点，那么skiplist里会有多少级索引呢？

按照上面的结构来推算：

第一级索引大约有 $N 2 N\over2$ 2N个节点。
第二级索引大约有 $N 4 N\over4$ 4N个节点。
第三级索引大约有 $N 8 N\over8$ 8N个节点。

依次类推，所以我们可以知道第M 级索引将大约有 $N 2 M \frac{N}{2^M}$ 2MN。假设索引的最高级T ，只有两个节点（头节点和尾节点），通过这个公式我们可以得知， $N 2 T = 2 \frac{N}{2^T}=2$ 2TN=2，所以最后我们可以得知最高级 $T = log ⁡ ( 2 N ) − 1 T=\log(2^{N})-1$ T=log(2N)−1，如果包含原始的链表，那么整个skiplist的高度就是 $log ⁡ ( 2 N ) \log(2^N)$ log(2N)。

所以skiplist的时间复杂度也就是O(log~2~N)。

空间复杂度 {#%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6}

相对于一个普通单向链表，一个skiplist需要额外存储多级索引，那这些额外的索引需要消耗多少空间呢？

这里还是假设有一个长度为N 的单向链表，根据上面我们得知从第一级索引开始每层的节点数分别是： $N 2 N\over2$ 2N、 $N 4 N\over4$ 4N、 $N 8 N\over8$ 8N... $8 8$ 8、 $4 4$ 4、 $2 2$ 2，每往上一层，节点就少一半，直到最后只剩下2个节点。就是一个等比数列。那么这些索引的总和也就是 $N 2 + N 4 + N 8 + . . . + 8 + 4 + 2 = n − 2 \frac{N}{2}+\frac{N}{4}+\frac{N}{8}+...+8+4+2=n-2$ 2N+4N+8N+...+8+4+2=n−2，所以我们可以得知skiplist的空间复杂度就是O(N)，也就是说如果将包含N 个节点的单向链表构造成skiplist，还需要额外再使用接近N个节点的存储空间。

结构设计 {#%E7%BB%93%E6%9E%84%E8%AE%BE%E8%AE%A1}

在源码server.h第930行可以看到定义了一个叫zskiplist的结构：

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

*header：指向头节点的指针，可以通过这个指针在O(1)的时间复杂度内定位到头节点。
*tail：指向尾节点的指针，可以通过这个指针在O(1)的时间复杂度内定位到头节点。
length：记录了skiplist的长度，也就是skiplist包含的节点数量（不包括头节点），可以在O(1)的时间复杂度内返回skiplist长度。
level：记录了skiplist的最大层数，可以在O(1)的时间复杂度内最大层数。

节点的结构 {#%E8%8A%82%E7%82%B9%E7%9A%84%E7%BB%93%E6%9E%84}

而skiplist的节点的结构则在源码server.h第920行：

typedef struct zskiplistNode {
    /* 成员对象 */
    sds ele;
    /* 分值 作为索引 */
    double score;
    /*后退指针，用于从后往前遍历使用 */
    struct zskiplistNode *backward;
    /* 节点的层结构 数组 */
    struct zskiplistLevel {
        /* 前指针 */
        struct zskiplistNode *forward;
        /* 跨度，用来确定本节点再链表中的排位  zrank */
        unsigned long span;
    } level[];
} zskiplistNode;

ele：每个节点保存的成员对象，在同一个skiplist中，每个节点保存的成员对象必须是唯一的，但是多个节点保存的score（分值）却可以是相同的。

score（分值）相同的节点将按照成员对象在字典排序中的大小来进行排序，成员对象较小的节点会排在前面，而成员对象较大的节点则会排在后面。
score：在skiplist中，每个节点按各自所保存的分值从小到大排列。
*backward：指向位于当前层的前一个节点，在从后往前遍历时使用。与前进指针所不同的是每个节点只有一个后退指针，因此每次只能后退一个节点。
zskiplistLevel：节点的层结构，每个层结构都有两个属性分别是*forward和span（前进指针和跨度）：
1. *forward：用来访问位于表尾方向的其他节点
2. span：记录了*forward（前进指针）所指向节点和当前节点的距离（也就是跨度越大，距离越远）。