redis补充说明之跳跃表

2670阅读 0评论2019-07-21 stolennnxb
分类:NOSQL

跳跃表是一种有序数据结构,它通过在每个节点中维护多个指向其他节点的指针,从而达到快速访问节点的目的。
redis使用跳跃表作为有序集合键的底层实现之一。redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构。
这里要说明以下的就是每个节点当中的跨度属性即span,这个属性记录了两个节点之间的距离,跨度越大,它们相距就越远。
在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分值相同的节点将按照成员对象在字典序中的大小来进行排序。
跳跃表的api列举如下
函数 作用
zslCreate 创建一个新的跳跃表
zslFree 释放给定跳跃表,以及表中包含的所有节点
zslInsert 将包含给定成员和分值的新节点添加到跳跃表中
zslDelete 删除跳跃表中包含给定成员和分值的节点
zslGetRank 返回包含给定成员和分值的节点在跳跃表中的排位
zslGetElementByRank 返回跳跃表在给定排位上的节点
zslIsInRange 给定一个分值范围,如果给定的分值范围包含在跳跃表的分值范围内,返回1,否则返回0
zslFirstInRange 给定一个分值范围,返回跳跃表中第一个符合这个范围的节点
zslLastInrange 给定一个分值范围,返回跳跃表中最后一个符合这个范围的节点
zslDeleteRangeByScore 给定一个分值范围,删除跳跃表中所有在这个范围之内的节点
zslDeleteRangeByRank 给定一个排位范围,删除跳跃表中所有在这个范围之内的节点

上一篇:redis源码阅读关于字典的一点补充
下一篇:redis补充说明之对象