Redis源码剖析——跳表(二)
下面进入跳表的具体实现,以下代码位于z_set.c
先忽略插入与删除中对span相关的调整操作,下一篇会专门对span进行解释后再继续跳表的后续剖析
以下是两个基本的创建函数
创建一个跳表节点,不多说
创建整个跳表。设置跳表的初始最大层高为1,长度为0。创建一个score为0,sds字符串数据域为NULL的头结点,同时该头节点的的高度应设为高度最大值,因为要保证未来无论出现多高的节点都不应高过头节点。最后把头节点的backward指针指向NULL,又因为当前跳表中还没有元素,故尾节点tail填充为NULL。
以下是两个基本的销毁函数
销毁一个节点。先销毁节点上的sds字符串,再销毁节点本身。
销毁整个跳表。头节点直接调用zfree而不是zslFreeNode,因为头节点并不需要释放节点本身,其上没有需要主动释放的sds字符串。在其他节点一一被zslFreeNode释放后释放整个跳表结构。
随机一个层数,不多说
在创建与释放后我们来看插入与删除的基本操作
插入分为两步
1、搜索更新点
2、通过更新点进行插入
以下为搜索更新点的逻辑
以下为实际插入的逻辑
以下是基本的删除操作
删除一个元素
接下来是删除一个节点的实现,这只一个跳表的内部函数,被跳表的其它函数调用
关于zrangespec结构有必要再具体说一下,其中min,max表示范围的区间断点很显然,至于minex与maxex则是表示是否取端点min、max,当minex被设置为非0时不取min端点,maxex被设置为非0时不取max端点,例如当判断一个score是否在某个区间内会通过如下两个函数进行判断
如下利用这两个函数实现判断整个跳表至少与一个区间有一部分交集
-
若是跳表本身中还无元素,说明跳表与区间不会有交集
-
若跳表尾端的score小于(或小于等于)区间的左端,说明跳表与区间不会有交集
-
若跳表中第一个节点大于(或大于等于)区间的右端,说明跳表与区间不会有交集
利用该函数实现返回跳表中第一个在range区间中的节点
类似的实现,返回跳表中最后一个在区间range中的节点
删除score在range区间内的所有节点
剩下的一些实现与span有关,在下一篇详细讲解
- 原文作者:Fh
- 原文链接:http://fhstack.github.io/post/2019-05-05-redisyuanmapouxitiaobiaoer/
- 版权声明:本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,非商业转载请注明出处(作者,原文链接),商业转载请联系作者获得授权。