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