Redis设计与实现(四)跳跃表

跳跃表是一个有序的数据结构,跳跃是通过在当前节点存储多个其他节点的指针,来达到跳跃的目的。它支持平均O(LogN)、最差O(N)复杂度的节点查找,还可以通过顺序性来批量处理节点。在大部分情况下,跳跃表的效率和平衡树是一样的,但是逻辑上比平衡树更加简单。

Redis通过跳跃表实现有序集合键的底层实现之一。在跳跃表中只有两个地方使用到了跳跃表,一个是有序集合键,另外一个则是在集群情况下作为内部数据结构。

Redis内部的跳跃表是由zskiplistNode和zskiplist这两个组成的。zskiplistNode表示跳跃的节点,zskiplist结构则表示用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。

 zskiplist存储了头节点和尾节点,以及目前节点中层数最大的值,以及节点的个数。zskiplistNode则存储了层(包含了前进指针以及跨度)和后退指针。上面图片中箭头表示了前进指针,上面的数字表示了跨度。

层:level数组可以包含多个元素,每个元素都有一个指向其他节点的指针。程序可以通过这些层,来加快访问其他节点的速度,每次新建一个节点的都会随机生成一个1-32之间的值来作为level的数组大小,这个大小则是数组的高度。

前进指针:每一层都有一个指向表尾方向的前进指针,用于从表头向表尾方向访问节点。

跨度:跨度用来记录两个节点之间的距离。这边注意的一点是跨度和遍历无关,遍历只需要知道下一个节点的位置就行了,跨度是用来计算节点的mark的,例如你知道你要找的是哪一个,打个比分是sroce是3的,那么有可能就可以直接获得,如果是找2的,那么从L2开始进行就可以很快的找到。

 

 节点的score是一个double类型的数据,节点的成员对象则是SDS,在同一个跳跃表里面各个节点保存的成员对象需要是一致的。但是多个节点保存的分值却可以相同;分值相同的节点可以按照成员对象在字典中的大小来进行排序。说白了 跳跃表就是通过维护有序,按照sroce来实现快速定位。

  

smartcat.994
原文地址:https://www.cnblogs.com/SmartCat994/p/14143884.html