• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

redis源码阅读之zskiplist

redis 海叔叔 22小时前 4次浏览 已收录 0个评论

作为zset的底层实现之一(另一个是dict),今天来扯扯zskiplist(跳跃表)这个东西,至于zset是怎么利用这两个东西的,咱们之后再表,这次只是说说跳跃表的实现。
跳跃表是一种有序的数据结构,它通过在每个节点中存放多个指向其他节点的指针(正向的指针>=1个,反向的指针就一个)来达到快速访问节点的目的。在redis当中,其代码定义如下:

先来说说zskiplistNode结构:

字段名称 含义
ele 当前节点存储的元素
score 当前节点存储的元素的得分
level[] 当前节点向前遍历时的指针数组,数组中的每个元素包含两个属性:1). 可以到达的节点指针forward;2). 该节点与当前节点的距离span,span用于计算forward节点在当前zskiplist当中的排名,而非用于遍历。
backward 当前节点向后遍历时的指针。注意这里不是数组,也就是说反向遍历只能从后往前一个一个来~~~

之后是zskiplist结构

字段名称 含义
header 指向跳跃表的头结点的指针
tail 指向跳跃表的尾节点的指针
length 跳跃表的长度,即当前跳跃表包含的节点数目(头结点不包含在内)
level 跳跃表中,level数组中元素最多的那个节点的level数组的元素个数(头结点不包含在内)

zskiplist结构当中需要多说一下的就是为什么length和level字段没有包括头结点?原因在于当创建一个zskiplist的时候,会直接把头结点设置成最大level,以便后续操作,其创建代码如下所示:

至于对zskiplist的操作方面,个人觉得还是得推插入和删除了
由于zskiplist当中不允许存在相同的sds,这一保障性工作交由调用插入操作的调用者来保证~
插入的时候需要注意的就是它是以level从大到小的顺序来遍历并更新各个指针的,详情见代码:

zskiplistNode创建的时候会随机生成一个介于1和32之间的数来决定level数组的大小,这个数的生成遵循“越大的数出现的概率越小”这一原则,代码如下:

节点的删除工作就比较的中规中矩了


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址