Redis源码剖析——跳表(一)

/ 0评 / 0

从跳表(SkipList)开始,离Redis用户层面就比较近了,Redis用户层面的五个基本数据类型中有序集合zset的实现主要基于三个部分:跳表、dict、ziplist。三者搭配的很完美,其中dict我们已经研究过,至于ziplist则是压缩列表,关于ziplist还会在稍微后面一点,那时候我会全面的给出zset是如何搭配这三者的。下面我们主要剖析zset中的跳表部分

关于跳表的基本实现的参考资料非常的多,在下文你必须已经了解与熟悉跳表,因为我们的重点是Redis中的实现,而不是教会你怎么去写一个跳表(虽然Redis中的跳表实现是绝对是范式级别)


预热

集合类型set中的元素是一个个的key,有序集合zset就是额外增加了一个score,可以理解为得分,score就是zset类型的排序码,通俗来说,有序集合中的key会按其对应的score的大小进行排序

对于一个排序的结构,你第一反应是什么呢?红黑树、AVL-Tree、B-Tree,毕竟广泛使用于大量场景,linux内核与数据库,但是Redis没有使用这二者,而是使用了一个略微少见的结构——跳表,跳表不是新鲜东西,实际上他很年纪很大了,比我大,不出意外应该也比你大,跳表最早在1990年由 William Pugh 在其论文 Skip Lists: A Probabilistic Alternative to Balanced Trees 中提出,在此引用其摘要:

Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

关于其中提到的概率模型我不作多说,其中说了一个很重要的事,那就是更简单(simpler),实际上快多少不算很重要,因为红黑树也够快了,但是对于Redis这样一个大型项目于来说,简单真的很重要,简单意味着后期方便维护与debug。

跳表本身的思路也真的相当简单,以下简单引用自wikiPedia

跳跃列表是一种数据结构。它允许快速查询一个有序的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n),优于普通队列的O(n)。 

image.png

跳表的快速查询是通过维护一个多层次的链表实现的,每一层链表中的元素是前一层链表元素的子集(见上边的示意图)。一开始时,算法在最稀疏的层次进行搜索,直至需要查找的元素在该层两个相邻的元素中间。这时,算法将跳转到下一个层次,重复刚才的搜索,直到找到需要查找的元素为止。


Redis中的跳表用于zset实现的一部分,代码部分位于server.h、部分位于t_zset.c,主要相关函数的声明与基本结构的定义在server.h中

下面是跳表基本结构的定义与主要相关函数的声明

image.png

跳表节点的定义。节点内存放的数据类型是sds字符串,score为排序码,内部结构体zskiplistLevel中forward则是一层中链表的next指针,span会专门有一篇详说,在此就先不展开了。level数组的长度就代表了该元素占据的层数,通过数组的随机访问即可实现向下跳(这里又使用了柔性数组)。

关于backward得专门说明一下,backward指针可以获取前一个节点,但是这个只在第一层为什么backward不用放在level数组里?因为这个backward仅仅只连接第一层了,backward指针在逆序获取的操作里是比较有用的,即将某个范围内的元素按score逆序返回

image.png

跳表的大结构,一个头、尾指针,记录元素个数的length,跳表的层数level为最高的节点的层数

image.png

这两个结构用于批量处理,其中zrangespec为按一个score区间进行批量处理,例如获取某个socre范围内的元素。

zlexrangespec为按字符串字典序进行批量处理,其中lex即Lexicographic。关于这一部分的实现主要涉及一些redis中对象的编码细节,这个留在后面,因此与lex相关部分暂时略过。

以下为跳表所有的基本方法(除去与lex相关)

image.png

跳表的最大层高及与随机层数有关的概率值

image.png


Redis中的跳表实现与William Pugh论文中的实现有两点不同

1、key(即我们的score)可以重复,因为比较时不仅比较key还比较对应的data(即我们的sds字符串),关于这个在下一接具体实现中会看到

2、第一层是一个双向链表

发表评论

电子邮件地址不会被公开。 必填项已用*标注