跳跃表计算排名的O(logN)实现

转载自
https://yuerblog.cc/2019/02/13/skiplist-rank/

做游戏的一般都有游戏排行榜的需求,意思就是查一下某个uid的积分排名第几。

这种数据结构其实就是redis里的zset实现,底层其实涉及2个关键数据结构:

  • 哈希表:维护uid -> score的映射关系
  • 跳表:维护score的从小到的有序关系

只要我们先从哈希表找到score,再去跳表里获取这个score的排名(rank)即可。

跳表与二叉树

为什么跳表可以高效的获取rank呢?只能说跳表的数据结构设计巧妙。

跳表本身提供的功能类似于平衡二叉树以及高级变种,可以对目标值进行快速查找,时间复杂度为O(lgN)。但是跳表的实现原理比实现一颗高效的平衡二叉树(比如红黑树)要简单太多,这是跳表非常大的一个优势。

关键在于,跳表计算某个score的排名次序,与在跳表中找到这个score的时间复杂度是一样的,仍旧是O(lgN)。反观二叉树系列,它们找到一个值也很快,但是要想知道这个值排名第几,似乎只能按照先序遍历的方式来统计排在前面的值个数。

其实跳表获取排名的思路也是数一下前面有多少个值,但因为”跳跃”的关系,统计的过程被加速了,因而rank效率更高。

跳表find原理

因为rank的计算过程,实际是伴随find某个score同时进行的,所以首先得知道find是如何进行的。

跳表本质上就是多层索引的链表,上述图中最下面一排是level1索引,串联了跳表中所有节点:5,11,20,30,68,99,跳表数据结构保证了插入位置有序。

每个节点的高度是随机确定的,所以有的节点可以串联到level2或者level3等更高层的链表中。跳表实现确保了,如果节点是高度3,那么会同时串联在level1,level2,level3的链表中。

当然,跳表不是真的随机确定插入的节点高度,而是让高的节点更少,矮的节点更多,最终产生的效果就是上图中的效果,即Level3链表的节点很少,而level2链表的节点多一些,level1链表串联了所有的节点。

当我们要查找数字68的时候,我们会先header节点的最高层链表level3开始向后查找,发现68>20则走到20节点上;发68<99则降低高度到level2;发现68>30则走到30节点上;发现68<99则降低高度到level1;发现68==68,找到了目标节点。

为什么要从最高层链表开始呢?因为高层链表串联的节点之间稀疏,跨度大,所以可以快速推进;一旦发现高层链表没有线索了,则需要下降高度到更稠密的链表索引中,继续向目标推进;直到某一个高度的链表索引中找到了目标;或者到最低层链表也没有找到目标,则说明目标值不存在。相反,如果我们直接从最底层链表向后查找,性能就蜕化为一个普通链表了,当然最终一定能找到目标/找不到目标,但就缺少了”跳表”的机会了。

跳表insert原理

插入和查找过程类似,但需要多做一点事情。

这里是插入数字80,白色是最终插入的位置,蓝色是此前就有的节点。

我们依旧从header节点的level3开始向后推进,每次下降level之前把当前level所处的node记录下来,也就是图中红色圈出来的节点。

然后,我们随机确定了80节点的高度是2,那么接下来各个level的链表该如何建设呢?奇迹就出现了,我们在每一level用红色圈出来的节点,其实就是每一level刚好小于80的那个节点,可以作为80在该level的链表前驱

因为80节点高度定位了2,所以插入到了level1和level2这两层链表,其中level2对整个跳表做出了突出贡献,因为80和30之间跳过了68,可以为之后的目标查找贡献自己的跳板能力。

跳表delete原理

删除一个节点比较简单,其实还是先逐级下降找到目标节点,用红色圈出每一level的前驱。

这里删除80节点:

需要注意,对于每一level中的红圈节点,需要判断其后继是不是80,如果是才需要在该level链表中摘除,否则说明该level没有串联80节点。

跳表rank原理

之前说过,跳表计算rank实际是经历了一次对目标值的查找过程,并在这个过程中累加出来的。

在跳表中,会为每个节点在每一level维护下一跳的距离span值,比如level3中从header节点跳到20节点,实际跨越了5,11,所以header在level3的span=3。

随着对目标值68的查找,我们在不同level向右移动的过程中就只需要累加span,比如在level2中20跳30就只需要1步,所以span加1即可,最终我们可以得到68的rank其实就是3+1+1=5,即排名第5,其前方的数字是5,11,20,30,就是这样一个原理。

那么问题就是每个节点在不同level的span怎么维护比较高效?其实在插入/删除的过程中,我们可以顺便就把span更新了。

回到这张插入80的图片。

我们先圈出了在level1~3的3个前驱节点(20,30,68),它们在整个跳表中的rank我们都可以在推进过程中累加出来。

在level2,80链到30的后面,怎么算出30的span=2呢?首先我们知道68的rank,所以就知道80的rank=68的rank+1;我们也知道30的rank,所以用80的rank – 30的rank,就是30跳到80越过的节点个数,也就是30的span。

在level3,80链在68的后面,怎么算出68的span=1呢?一样的道理,我们知道68和80的rank,做减法就是68的span。

上述已经把受影响的前驱节点的span更新完成了,但是新插入节点80的span还没设置

其实我们在更新30和68的span之前,知道30和68的旧span值(30到99和68到99的跳数)。对于level2来说,只需要用30的旧span-30的新span就是80在level2的新span值。对于level3来说,只需要用68的旧span-68的新span就是80在level3的新span值。

这就可以了吗?

上面的有几张图片是错误的,它们在level3的20没有连到99上,在跳表中这是不可能存在的,一定会有索引链过去,这是网上的错误图片。

我们脑补一下最后一张图片中缺失的那根线,然后想一下level3的20的span的值需不需要更新?

答案当然是需要了,因为在20和99之间插入了一个80,这要是level3中20跳跃到99要经过的节点。

所以,对于高于插入节点的level,我们需要对圈红的节点的span+1处理。

最后

删除节点更新span比较简单,留给大家思考。

发表评论

电子邮件地址不会被公开。 必填项已用*标注