游戏排行榜 – 基于skiplist计算rank排名

On By yuer

做游戏的一般都有游戏排行榜的需求，意思就是查一下某个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比较简单，留给大家思考。

其实跳表我5年前就用C实现过，只是那时候没有想过它还有rank的这个功能，今天把它代码补充了上去：跳表C实现。

工作久了，以前天天钻研的数据结构和算法都还回去了，现在只剩下CRUD的本领，哎。

如果文章帮助您解决了工作难题，您可以帮我点击屏幕上的任意广告，或者赞助少量费用来支持我的持续创作，谢谢~