实时排行榜的几种实现方案

实时排行榜要求实时，不能有延迟。要实现此，就必须是插入时排序，而不能读取时排序。读取时排序的工作量非常之大。这里列几种可能的方案。

桶排序

在游戏开发中，大部分时候需要对分数做排行榜。比如，分数区间在1-5000，但用户可能有几百万个。显然在这种场景下很多人都是相同的分数。此时就可以把1-5000设计成5000个桶，然后把每个用户按照自己的分数分别放入对应的分数桶。

要查询实时排行榜topN只需要把分数高的前面几个桶合起来展示就可以了。

桶排序

redis实现

使用redis的sorted set来排序。sorted set是一个有序列表。你可以使用zadd、zrange以及zrank轻松实现实时的排名。

添加三个人的分数

获取所有人（包含分数）

倒序获取所有人（包含分数）

获取张三的排名（正序）

获取张三的排名（倒序）

redis的sorted set是用skip list（跳表）算法实现的。时间复杂度为O(log(N))。skip list是一个基于链表然后额外创建父链表，从而使得链表的查找效率得到提高。另外由于skip list插入一个元素，只需要修改前驱和后继的引用即可轻松插入一个元素，所以性能也要比平衡树还要好（平衡树要各种旋转）。

平衡树

java的treemap是基于红黑树来实现。可以尝试通过treemap来实现排行榜。

通过这种方式来实现需要解决几个问题：

1、分数相同时怎么解决？我目前想到的是通过分段来决定唯一。设置小数点后几位为用户ID。

2、如何实时获取到指定用户的分数以及排名？

抛砖引玉一下，欢迎说出你的方案！