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

/ 0评 / 0

Redis跳表中每个节点的span实际上是个非常巧妙的设计,但是关于span的部分阅读起来不是很容易,因为这种在数据结构上做的创新行为往往不能第一眼就理解。在跳表的插入删除操作,可以看到有很多部分都在对span进行调整,span是一个重要且不能绕过的东西,那么span到底是用来干什么?调整span到底是在做什么?


我们知道span是跨度的意思,这个跨度到底代表了什么意义?

思考一个问题:如何在在跳表中遍历一趟就得出一个节点在跳表中的排位(指节点是跳表的第几个节点)?

是不是个简单事儿?毕竟跳表不是链表,链表一个一个往后走要找出一个节点的排位当然很简单,你也许会说:那我们遍历跳表的第一层不就行了吗?当那就不是跳表了......

Redis的跳表中提出了一个方案:记录每层中两个节点间的跨度,所谓跨度即这两个节点间的距离,注意这个距离是真正的距离,不是仅仅对本层而言的距离,而是对应在第一层中的距离,如下图(图片修改自wikiPedia)

image.png

其中红色括号里的数字就是每个节点的span,即节点自身与本层下一个节点间的跨度,很清楚把?通过这个跨度,比如我们要找5,那么把寻找5的路径上每个节点的span累加起来,这样便得到了节点5在跳表中的排位 1 + 3 + 1 = 5(不过在具体实现中会看到排位是从0开始,但是0对应的是header节点,跳表中的有效节点的排位仍然从1开始)

弄明白这个后,再回过头看看插入与删除中关于span的部分(建议结合图理解)


先看插入的两部分

搜索更新点

image.png

插入并进行相应调整

image.png

再看看删除一个指定节点中span的调整

image.png

也有可能你仍然不太理解span......别灰心,不得不承认span相关的部分阅读起来比较难受,若你看到这还不理解建议自己画一画过程~


下面是按rank闭区间批量删除节点

image.png

以下为获取一个元素(score+sds)的排位(rank)

image.png

注意,节点的排位是从1开始的,因为0对应的是header节点,若是返回0则表示要搜索的元素不在表中

以下为获取指定排位的节点,同样,排位仍然从1开始

image.png

可以看到,上面这三个函数都通过span得到了非常高效的实现


跳表到此也就结束了,在后面剖析完ziplist后就可以将skipList、ziplist、dict进行串联构成zset的完整实现。



发表评论

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