Redis底层数据结构之跳表（SkipList）

        SkipList是Redis有序结合ZSet底层的数据结构，也是ZSet的灵魂所在。与之相应的，Redis还有一个无序集合Set，这两个在底层的实现是不一样的。

标准的SkipList：

        跳表的本质是一个链表。链表这种结构虽然简单清晰，但是在查询时的效率比较低（O(n)），而在有序集合的场景中，我们希望运用有序这个前提条件，来提高我们增删查的效率。在算法中，有一种针对有序集合的搜索算法叫二分查找，Redis中的ZSet底层在设计时也参考了二分查找的思想，引入了跳表。跳表在链表的基础上，引入了多级索引，通过索引可以一次实现多个节点的跳跃，提高查询性能，下面是跳表的结构图：

        可以看到，图中的某些节点不光只有一层。如果使用普通的节点，那么每一步只能查询后方的一个节点，如果用这种有高层的节点，那么可以实现一步查询后方相隔多个的节点。理论上，层次越高，对应的步长就越大，但是实际上并不像上图一样是绝对均衡的，节点的层高其实是概率随机的，下面会具体分析到，这里我们先这样简单理解。

        为了理解这种结构有什么好处，我们根据上方的图分几个来进行分析。

        （1）查找分数为35的数据。

        如果只有原始链表的话，那需要走4步，如果有图中的二级索引，那么只用走一步。如果要找的值是45呢？其实就是从第一个节点出发，通过二级索引走到节点值为35，再查看二级索引对应的下一个节点值为65，已经超过要查询的节点值，所以在值为35的节点上，二级索引下降到一级索引向后遍历，再走一次就到了值为45的节点。整个查询的过程其实和二分查找十分相似。

        （2）插入一条score为36的数据。

        要插入一个值为36的节点，那么我们首先应该定位到一个值比36大的节点，也就是图中值为45的节点，定位的方式与查询类似。然后构造一个新的值为36的节点，这里我们假设节点的层高随机到3,（具体的随机算法我们后面会讲），最后将各层链表补齐，其实就是在每一层进行链接，完成后效果如下图所示：

        标准的跳表会存在如下两种限制：

        ①score值不能重复，也就是在底层链表中不允许存在两个值相同的节点。

        ②底层链表只有前向指针（next），而没有退回指针（prev）。

Redis中的SkipList：

        在Redis中，跳表是用来支持有序集合的，所以Redis对标准跳表做了一些优化，使得链表中的score值可以重复，并且增加了回退指针，具体的结构如下图所示：

zskiplistNode：

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

        ele：用来存储数据，使用的是SDS数据结构。

        score：用来存储节点的分数，采用double数据类型。

        backword：指向上一个节点的回退指针，支持链表从尾到头的遍历，也就是ZREVRANGE这个命令。

        level[]：level结构体数组是用来保存各个索引层级的forward指针和span信息的。具体来说，level[0]存储的就是第一层索引（最底层索引），level[1]存储的就是第二层索引，以此类推。higher level的forward指针可以指向更远的节点，可以用来快速遍历。span记录索引跨度。通过维护多级索引，跳表可以通过较高层级的索引快速定位到目标节点附近，然后再在底层索引进行线性查找。所以，level数组在跳表中的作用就是记录多级索引的数据，让跳表可以实现更快的查找、遍历、排序等操作。

zskiplist：

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

        *header：指向跳表的头结点（头结点不存储任何数据，并且其level数组的大小为32）。

        *tail：指向跳表的尾节点。

        length：存储跳表中除去头结点后其余节点个数。

        level：存储跳表中除去头结点后其余节点中level数组最大长度。

内存分布：

        Redis中的SkipList内存分布如下图所示：

        

Redis中跳表的Node中的level数组长度怎么决定？

        长度的决定需要比较随机，才能在各个场景中表现出较为平均的性能。Redis使用概率均衡的思路来确定新插入节点的层数：Redis跳表决定每一个节点，是否增加一层的概率为25%，而最大层数限制在Redis5.0时是64层，在Redis7.0时是32层。

Redis使用跳表对性能究竟优化了多少？

        与二分查找的平均时间复杂度是一样的，Redis使用跳表将增删查的时间复杂度从O(n)降低到了O(logn)。

Redis为什么不使用哈希表或者平衡树？

        先来看一看作者是怎么回答这个问题的：

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.About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.
About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.

        说人话就是跳表的实现更加简单，并且达到了类似的效果。

        首先回答一下为什么不使用哈希表。最大的原因就是哈希表的存储是无序的，因此哈希表更适合解决对单个键的查询工作，而不适合解决范围查找问题（查找哪些值在两个数之间的节点的这类问题）。

        接着回答为什么不使用平衡树。平衡树可以解决范围查找的问题，但是与SkipList相比，平衡树在进行范围查找时的操作更加复杂，当我们在平衡树上找到指定范围的小值时，还需要以中序遍历的顺序继续寻找其他不超过指定范围的大值的节点，而SkipList的操作就很简单了，只需要在找到小值之后，进行若干步的遍历即可。平衡树在进行插入和删除操作时可能引发树的自平衡调整，逻辑复杂，而SkipList在进行指定节点的插入和删除时，只需要修改相邻节点的指针就可以了，逻辑和操作都很简单。

        所以，Redis在实现复杂度和性能上，最终选择的是SkipList数据结构。

        Redis底层数据结构篇文章到这里就迎来一个小结了，有什么问题或者勘误欢迎评论区留言，笔者看到都会回复的。