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

17条回复

做游戏的一般都有游戏排行榜的需求，意思就是查一下某个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的本领，哎。

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

《游戏排行榜 – 基于skiplist计算rank排名》有17个想法

  1. Pingback引用通告： 跳跃表计算排名的O(logN)实现 – 孙哥我还是看不透生死

  6. ラブドール

    ラブドール通販店 | ブランド正規品 | 最安値直販店 https://otona-love.jp/
    おとなLOVE (otona love) は正規直販店であり、自分の生産現場を持っております。第三者に通らず生産現場から直接顧客に配送するため、TPE素材や高級シリコン製のラブドールを低価格高品質で入手できます。また、正規代理WMDOLLラブドール、6YEDOLLラブドール、JY DOLLラブドール、メーカーから直接消費者の手元に届くようなサービスを提供させていただきます。品質保証、安心・安全への取り組み。また、新着ラブドール 特別価格¥59999円から（税込み） 新着分解型ラブドール特別価格¥66,999円から（税込み）

    回复 ↓
  13. nipple stimulating toys

    Nipple corrector set: the package contains 8 pieces of nipple corrector items, including 2 pieces of nipple suckers, 2 pieces of nipple aspirators, 2 pieces of nipple pullers, and 2 pieces of nipple protectors; The whole set of nipple corrector help newborn mothers and women to improve their flat or inverted nipples

    回复 ↓
  14. sexual toys online

    When you’re working on changing your sex life, you pay attention to how outrageous the supermarket or adult sex store prices are. In fact, you are willing to invest in sex toys. But the “adult store near me” is expensive. Well, you should know more. Because sometimes you don’t have to spend that much to have a top-quality sex toy.

    回复 ↓

发表评论

您的电子邮箱地址不会被公开。