https://juejin.cn/post/6963096695333158926
https://blog.csdn.net/weixin_41701290/article/details/118313087
https://juejin.cn/post/6885139963298611214

小顶堆

1亿个数找到1000个最大值其实就是找1亿个数中前1000大的数，首先以一亿个数字中的前1000个数建立小顶堆

这样我们可以保证这前一千个数字的堆顶是最小的（因为小顶堆的的堆顶是小于它的左右孩子的）这样我们依次比较 1000之后的数字一直到第1亿个数，例如：第1001个数和小顶堆的堆顶比较，如果比堆顶小的话那么它一定比1000个 数这里面的任意的数都小，所以不可能是前1000大的数，如果第1001个数比小顶堆的堆顶大的话，那么这个堆顶就一 定不是前1000大的数，所以此时这个第1001的数代替这个堆顶，代替堆顶之后此时的小顶堆已经不一定是小顶堆了 所以我们需要进行堆调整，来使其变成小顶堆。 堆调整的过程其实就是依照小顶堆的特点（堆顶比左右孩子小）， 如果堆顶大于左右孩子就将其与对应孩子交换，交换后左右孩子再和它的左右孩子进行比较。一直进行到不比左右 孩子大为止。

对应JavaScript代码如下：（在此将1亿改成20，将1000改成8，20个数中找到8个最大值）

var N = 8;         //Top10
var LEN = 20; //1亿个整数
var arrs = []; // 装1亿整数的数组
var arr = [] ; // 装十个整数的数组
//数组长度
var len = 8;
//堆中元素的有效元素 heapSize<=len
var heapSize = len;
//生成随机数组
for (let i = 0; i < LEN; i++) {
    arrs[i] = Math.floor(Math.random() * 50);
}
console.log(arrs)
//构建初始堆
for (let i = 0; i < N; i++) {
    arr[i] = arrs[i];
}
// 初次建立size = 10的小顶堆以这十亿个整数中前10个数
console.log(arr)
//构建小顶堆
buildMinHeap(); // 将这前十个数每个非叶子结点 堆调整建立小顶堆
// 此时arr是以前十个arrs组成的小跟堆
for (let i = N; i < LEN; i++) {
    // 此时模拟数据流 从第11个到第一亿个数分别进入 和小跟堆的堆顶比 比堆顶小的话就被淘汰，
  // 比堆顶大的话将其和堆顶交换，进行堆调整
    if (arrs[i] > arr[0]) {
        arr[0] = arrs[i];
        minHeap(0);
    }
}
console.log('一亿里面前十个元素', arr)
/**
 * 建小顶堆
 */
function buildMinHeap () {
    let size = Math.floor(len / 2);
    for (let i = size; i >= 0; i--) {
        minHeap(i);
    }
    console.log('初小跟堆', arr)
}
/**
 * i节点为根及子树是一个小堆
 * @param i
 */
// 堆调整的筛选
function minHeap (i) {
    var l = 2 * i + 1; // 左孩子
    var r = 2 * i + 2; // 右孩子
    var t // 存交换的暂时参数
    var index = i; // index 存最小坐标
    if (l < heapSize && arr[l] < arr[index]) {
        index = l;
    }
    if (r < heapSize && arr[r] < arr[index]) {
        index = r;
    }
    if (index != i) {
        t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;
        //继续堆调整
        minHeap(index);
    }
}

设计一个排行榜

其实扯了这么多，这就是个常见的面试场景题：如何设计一个排行榜？
这个题吧，其实就是考你面试准备范围的广度，见过就会答，没见过…就难说了。
当然，如果你在实际业务中做过排行榜，那么这题正中下怀，你也不要笑出声来，场景题面试官是会给你思考时间的。

所以你不要张口就来，你只需要眉头稍稍一皱，给面试官说：这题我想想啊。
然后稍微组织一下语言，说出来就行。
这次的文章，就带着大家分析一下“排行榜”这个场景题，到底应该怎么做。

基于数据库

这个题，如果是真的之前没有遇见过，可能最容易进入大家视野的就是平时接触的最多的数据库了。
因为一想到“排行榜”，就想到了 order by。
一想了 order by，就想到了数据库。
一想到了数据库…
兄弟，你路就走窄了。
虽然我曾经就基于 MySQL 做过排行榜，因为当时是为了一个比赛临时搭建的服务，根本就没有引入 Redis。我评估了一下搭建 Redis 的时间和用 MySQL 直接开发的时间。
于是选择了 MySQL。
而让我选择 MySQL 的根本原因还是我已经知道进入决赛的队伍只有 10 支，也就是说我的排行榜表里面从始至终也只有 10 条数据。
选手提交代码之后，系统实时算分，然后更新排行榜表。
然后接口返回给前端页面下面这些数据，而下面这些数据都在一个表里面：

• 队伍按照历史最高分数排名
• 队伍名称
• 历史最高分数
• 最近一次提交得分
• 最近一次提交时间

前端每隔一分钟调用我的接口，相同分数，名次相同，所以我在接口里面用一条比较复杂的 sql 去查询数据库，上面的这些字段就都有了。
你看，排行榜确实是可以用 MySQL 来做的。
不一定非得上 Redis，记住一句话：脱离业务场景的方案设计，都是耍流氓。

但是这玩意和“万物皆对象”一样，别对着面试官说，这一定不是面试官想要听到的答案。
或者说，这只是想要听到的一部分回答。
这个回答能用的原因是我给了一个具体的场景，用户量非常的小，怎么玩都可以。
甚至我们不借助 MySQL 的排序，把数据查出来，在内存里面排序都可以。
但是如果，这是一个游戏排行榜，随着游戏玩家的增加，达到千万用户级别的话，这个方案肯定是不行了。
当然，也许你会给我扯什么查询慢就加索引，数据量大就分库分表的方案。
怎么说呢，上面这句话是没有错的。
但是一旦数据量大起来了，这个方案其实就不是一个特别好的方案。
这问题，得从根上治理。

基于 Redis

这个场景其实就是在考察你对于 Redis 的 sorted set 数据结构的掌握。
sorted set，见名知意，就是有序集合的意思。
在 Redis 中它大概是长这样的：

前面的 sport:ranking:20210227 是 Redis 中的 key。
value 是一个集合，且可以看出这个集合是有序的。集合中的每一个 member 都有一个 score，然后按照这个 score 进行降序排序。
需要注意的是，图片中的 score/member 不是我随便写的，官网上就是这样定义的：
https://redis.io/commands/zadd#sorted-sets-101

而且官网上说的是： score / member pairs。
所以我画图的时候，score 在前，member 在后。这可不是随便画的，虽然谁前谁后好像也不影响什么玩意。
另一个需要注意的点是，虽然我的示意图中没有体现出来，但是在有序集合中，元素即 member 是不可以重复的，但是 score 是可以重复的。
这个很好理解，就比如 20210227 这一天的微信步数，我可以走 6666 步，你也可以走 6666 步，这个是不冲突：

但是，问题就随之而来了：当 member 的 score 一样的时候，member 是怎么排序的呢？
看一下来自官网的答案：

当多个元素具有相同的分数时，它们按照 lexicographically 进行排序。
哎呀，lexicographically 这个单词不认识。
不慌，你知道的 why哥还兼职教英文：

当分数一样的时候，按照字典序排序，所以上面的示意图 jay 在 why 之前。
接下来，看一下有序集合的操作函数，一共有 32 个：

我这里就不一个个的做 API 教学了，官网上已经写的很清楚了，如果对于不熟悉的命令，可以去官网上查看，都是有示例代码的。
https://redis.io/commands/zadd#sorted-sets-101
比如这个 ZADD 方法：

为了后面分享的顺利进行，我这里只讲几个需要用到的操作：

• 添加 member 命令格式：zadd key score member [score member …]
• 增加 member 的 score 命令格式：zincrby key increment member
• 获取 member 排名命令格式：zrank/zrevrank key member
• 返回指定排名范围内的 member 命令格式：zrange/zrevrange key start end [withscores]

先看第一个：添加 member。
比如我们把示意图中的数据添加到到有序集合里面去，语法是这样的：

• zadd key score member [score member …]

意思是可以一次添加一对或者多对 score-member，比如下面这两个命令：

• zadd sport:ranking:20210227 10026 why
• zadd sport:ranking:20210227 10158 mx 30169 les 48858 skr 66079 jay

执行之后，返回的数字代表添加成功的 member 个数。
我用专门操作 Redis 的 RDM 可视化工具来查看插入的数据，和我自己画的示意图相差无几：

接着看第二个：增加 member 的 score
微信运动排行榜的数据是实时更新的。
目前 member 为 why 的步数是 10268，假设我吃完晚饭出门跑步去了，又跑了 5000 步。
这时得更新我的步数，就用 zincrby 命令，语法是这样的：

• zincrby key increment member

对应上面场景的执行命令是这样的：

• zincrby sport:ranking:20210227 5000 why

执行完成后，会返回 why 的步数，可以看到从 10026 变成了 15026 ：

同时由于我的步数增加，按照 score 倒序，也导致了排序的变化：

所以我们只需要更新 score 就行了，至于排名的变化，Redis 会帮忙保证的。
然后看第三个命令：获取 member 排名
语法是这样的：

• 获取 member 排名：zrank key member
• 获取 member 排名：zrevrank key member

首先，排名都是 0 开始计算的。
zrank 是按照分数从低到高返回 member 排名。
zrevrank 是按照分数从高到低返回 member 排名。
比如现在要获取 jay 的排名，用 zrank 返回结果就是 4。

• zrank sport:ranking:20210227 jay

当用 zrevrank 时，jay 的排名就是 0：

• zrevrank sport:ranking:20210227 jay

所以，在微信步数排行榜的这个需求中，步数越多排名越靠前，我们应该用 zrevrank。
第四个需要掌握的命令是：返回指定排名范围内的 member。

• zrange/zrevrange key start end [withscores] 返回指定排名范围内的 member

这个命令就很关键了。
zrange 是按照 score 从低到高返回指定排名范围内的 member。
zrevrange 是按照 score 从高到低返回指定排名范围内的 member。
在这里，我只演示 zrevrange 的命令。
比如我要获取步数排名前三的 member：

• zrevrange sport:ranking:20210227 0 2

这个命令有个可选参数：withscores
当带上这个参数之后，会返回对应 member 的 score：

你想，这不就是排行榜 top N 的场景吗？
假设我现在要获取所有用户的排名，怎么写呢？
如下：

• zrevrange sport:ranking:20210227 0 -1

这就是当前的微信步数排行榜，jay 步数最多，mx 步数最少。
咦，怎么回事，排行榜好久就出来了呢？
你想想，讲完几个 API 操作，好像功能就实现了呢？
是的，确实是这样的，甚至我们只需要这两个 API 就能完成排行榜的需求：

• zadd key score member [score member …] 添加 member
• zrange/zrevrange key start end [withscores] 返回指定排名范围内的 member

好了，如果大家喜欢的话，感谢大家一键三连。本次的文章就到这里了…

那是不可能的。
索然无味的 API 文章多没有意思啊。
虽然前面的部分我们已经可以基于 Redis 的有序集合加上几个简单的命令，就可以实现排行榜需求了。
但是前面只是铺垫，接下来，好戏才刚刚开始。

再次审视排行榜

上面的微信步数排行榜有个问题，你发现了吗？
就上面这个场景而言，所有人来看，看到的都是这样的排序：

而真实情况是，每个人看见的数据排行数据来源自己的微信好友，而微信好友各不相同，所以看到的排行榜也各不相同。
这个特性，我们并没有体现出来。
我们上面的场景更加类似于游戏排行榜，所有的人看到的全服排行榜都是一样的。
那么怎么保证我们每个人看到的各不相同呢？
你思考一下，该从什么角度去解决这个问题呢？

有序集合的 key 不同，就获取到不同的 value 集合。
我们当前的 key 是 sport:ranking:20210227，里面只包含了某一天的信息。
只要我们在 key 里面加上用户的属性就可以了，假设我的微信号是 why。
那么 key 可以设计为这样 sport:ranking:why:20210227。
这样，由于 key 里面多了用户信息，每个人的 key 都各不相同，就像这样的：

对应的命令如下：

• zadd sport:ranking:why:20210227 10026 why 10158 mx 30169 les 48858 skr 66079 jay
• zadd sport:ranking:mx:20210227 7688 赵四 9688 刘能 10026 why 10158 mx 54367 大脚

why 和 mx 看到的都是各自好友某一天的微信步数排行榜。
只要把 key 设计好了，这个问题就迎刃而解了。
但是你仔细思考一下，真的就迎刃而解了吗？
这个问题，我在写第一版的时候可能是被猪油蒙蔽了双眼，没发现。
有种“只缘身在此山中”的味道，一心想着 Redis 了。
你想，如果每个用户都有在redis有一个自己的排行榜，一个用户的分数更新的时候就需要对所有好友的zset更新，这多大的代价啊，对吧？
当以用户为纬度做排行榜的时候，就会出现排行榜巨多的情况，导致维护成本升高。
Redis能做，但不是最佳方案。
那么用什么方案去做呢？
我提个思路吧：
每个用户看到的排行榜不一样，我们其实不用时时刻刻帮用户维护好排行榜。
维护好了，用户还不一定来看，出力不讨好的节奏。
所以还不如延迟到用户请求的阶段。
当用户请求查看排行榜的时候，再去根据用户的好友关系，循环获取好友的步数，生成排行榜。
具体方案，大家自己思考一下吧。
另外多说一嘴，前段时间不是微信支持了修改微信号吗，赢得一大片叫好声。
其实我当时认真的想了一下，从技术上的实现来说这个需求到底有多难。
我不知道有没有历史技术债务在里面。
但是就说当前这个场景，key 里面包含了微信号，注意是微信号，不是微信昵称。
因为在设计之初，产品打包票说：放心，微信号绝对全局唯一，一旦确定，不可变更。
结果呢，现在要变化了。
产品屁颠屁颠的说：怎么实现我不管，这个需求用户呼吁很大，赶紧上线。
你说，对这些类似场景的冲击有多大？
其实冲击也不算特别大，一个字段的变化而已。
但是，微信 14 亿用户啊。
一个简单的需求，涉及到这个体量之后，就一句话：
量变引起质变。
好了，好了，扯远了。说回来。

当我把目光再次放到微信排行榜上的时候，我发现，其实我只是给了一个阉割版的排行榜。
是的，我们现在可以获取到 why 的当前步数是 1680 步，当前排名是 814 名。
比如还是沿用上面的例子，假设现在要获取我的微信好友 jay 的微信步数排行榜情况。
先获取 jay 的名次：

• zrevrank sport:ranking:why:20210227 jay

名次为 0，程序里面可以对其进行加一操作。就是第一名了。
接着获取 jay 的今日步数：

• zscore sport:ranking:why:20210227 jay

66079，步数也有了。
现在我们知道了：why 的好友 jay 今日运动步数 66079 步，在 why 的微信好友中排第一名。
但是你仔细看，这上面我还漏了两个字段：

• 微信头像
• 朋友点赞个数

两个字段应该怎么放呢？
放数据库里面当然可以，但是我们主要还是说一下 Redis 的解决方案。
这个时候其实我们想要存储的是 User 对象，对象里面有这几个字段：昵称、头像图片链接、点赞数、步数。
你说，这个用 Redis 的啥数据结构来存？
可不就得用 Hash 结构了吗。
Hash 结构同样涉及到 key 和 value，那么它们分别是什么呢？
key 就是我们的有序集合的 key 后面再加上好友昵称，比如这样的：

对应的命令是这样的：

• hmset sport:ranking:why:20210227:jay nickName jay headPhoto xxx likeNum 520 walkNum 66079

执行完成之后，在 RDM 里面看起来是这样的：

当后续有更多的赞的时候，需要调用更新命令更新 likeNum：

• hincrby sport:ranking:why:20210227:jay likeNum 500

执行完成之后点赞数就会变成 1020：

这样，排行榜上的所有字段我们都能获取到了，微信排行榜就说完了。
呃……
怎么感觉还是 API 教学呢？
不得劲，换个其他的。

最近七天排行榜怎么弄？

前面我们说的都是每日排行榜。
假设面试官要求我们提供一个最近七天、上一周、上一月、上个季度、这一年排行榜啥的，又该怎么搞呢？
其实这还是在考察你对于 Redis 有序集合 API 的掌握程度。
也就是这个 API：

• zinterstore/zunionstore destination numkeys key [key …] [weights weight [weight …]] [aggregate sum|min|max] 获取交集/并集

这个 API 看起来有点复杂，不要怕，一个个的讲：

• zinterstore/zunionstore其实就是交集/并集
• destination 将交集/并集的结果保存到这个键中
• numkeys 需要做交集/并集的集合的个数
• key [key …] 具体参与交集/并集的集合
• weights weight [weight …] 每个参与计算的集合的权重。在做交集/并集计算时，每个集合中的 member 会把自己的 score 乘以这个权重，默认为 1。
• aggregate sum|min|max 对于各个集合中的相同元素是 sum(求和)、min(取最小值)还是max(取最大值)，默认为 sum。

拿最近七天举例，我们随便搞点数据进来，你可以直接粘过去玩：

• zadd sport:ranking:why:20210222 43243 why 2341 mx 8764 les 42321 skr
• zadd sport:ranking:why:20210223 57632 why 24354 mx 4231 les 43512 skr 5341 jay
• zadd sport:ranking:why:20210224 10026 why 12344 mx 54312 les 34531 skr 43512 jay
• zadd sport:ranking:why:20210225 54312 why 32451 mx 23412 les 21341 skr 56321 jay
• zadd sport:ranking:why:20210226 3212 why 63421 mx 53652 les 45621 skr 5723 jay
• zadd sport:ranking:why:20210227 5462 why 10158 mx 30169 les 48858 skr 66079 jay
• zadd sport:ranking:why:20210228 43553 why 4451 mx 7431 les 9563 skr 8232 jay

可以看到我们一共有 7 天的数据：

而且需要注意的是 20210222 这一天是没有 jay 的数据的。
现在我们要求出最近 7 天的排行榜，就用下面这行命令，命令有点复杂，但是对着命令格式看，还是很清晰的：

• zunionstore sport:ranking:why:last_seven_day 7 sport:ranking:why:20210222 sport:ranking:why:20210223 sport:ranking:why:20210224 sport:ranking:why:20210225 sport:ranking:why:20210226 sport:ranking:why:20210227 sport:ranking:why:20210228 weights 1 1 1 1 1 1 1 aggregate sum

这条命令后面的 weights 和 aggregate 都是可以不用写的，有默认值，我这里为了不隐藏数据，都写了出来。
执行完成后，可以看到多了一个 key，里面放的就是最近 7 天的数据汇总：

上面用的是并集，如果我们的要求是对最近 7 天，每天都上传运动数据的人进行排序，就用交集来算。
命令和上面的一致，只是把 zunionstore 修改为 zinterstore 即可。
另外为了有对比，合并之后的队列名称也修改一下，命令如下：

• zinterstore sport:ranking:why:last_seven_day_zinterstore 7 sport:ranking:why:20210222 sport:ranking:why:20210223 sport:ranking:why:20210224 sport:ranking:why:20210225 sport:ranking:why:20210226 sport:ranking:why:20210227 sport:ranking:why:20210228 weights 1 1 1 1 1 1 1 aggregate sum

从执行结果可以看出来，由于 jay 同学在 20210222 这一天没有上传运动数据，所以取交集的时候没有他了：

知道最近 7 天的做法了，我们又有每一天数据，上一周、上一月、上个季度、这一年排行榜啥的不都是这个套路吗？
呃……
怎么感觉还是 API 教学呢？
还是不得劲，再换个其他的。

亿级用户排行榜

王者荣耀，妥妥的亿级用户吧。比如我想看看我在亿级用户中排多少名，于是我打开了游戏，二十多分钟（玩了一局）之后我终于找到排行榜的位置。
结果，未上榜：

我这个千年老夫子，当然是未上榜了。
就算真的有排名了，排名好几千万，8 位数字，在页面上也不好放呀。
但是假设现在的需求就是要查询用户的全服排名，怎么查？
我瞎说一个我能想到的基于 Redis 的初版方案，注意是我瞎想的，实际做起来肯定是异常复杂的方案。
我是怎么想的呢？
我就寻思，一般面试遇到什么千万条数据、几个 G 文件、上亿的数据啥的，首先想到的方案就是分而治之。
这个亿级用户排行榜的需求也得用分治的思想。
王者一共 8 个段位：

• 1、倔强青铜
• 2、秩序白银
• 3、荣耀黄金
• 4、尊贵铂金
• 5、永恒钻石
• 6、至尊星耀
• 7、最强王者
• 8、荣耀王者

所以我们可以有 8 个桶。
这个桶可以是一个 Redis 里面的 8 个不同的 key，甚至可以是 8 个 Redis 里面各一个 key，看面试官给你的经费是多少，钱多就可劲造。
如下图所示：

解释一下上面的图片中 score 为 8588 是怎么来的。
首先我们用 Redis 的有序集合，那么我们就得给每个 member 一个 score。
所以，每个用户在桶里面都一个经过公式计算后得出的积分。
比如why哥现在的段位就是星耀，假设计算出来的分数是 8588。
那么现在要算why哥在全服的排名就很好算了：
写程序的时候是可以知道我现在的段位是星耀，那么直接去星耀的桶里面，用 zrevrank 计算出当前桶里面的排名，假设为 n。
然后再通过 zcard 这个 O(1) 的命令获取到，前面的桶，也就是最强王者和荣耀王者这两个桶的集合大小，分别为 y 和 x。
那么why哥的全服排名就是 n+y+x。
所以获取任何一个用户的全服排名，就是看他在自己的桶里面的排名加上前面桶里面的元素个数即可。
而且现在要计算全服 top 100 就很容易了嘛。
直接取最前面的桶，也就是荣耀王者里面的前 100 个就完事了。
搞定。

等等，真的搞定了吗？
思路是对了，但是对于亿级用户只分 8 个桶未免太少了吧？
那就继续分桶呗，别忘了，每个段位里面还有小段位的。
比如星耀，里面就有星耀五到星耀一五个小段位，青铜三到青铜一三个小段位。
全部算上就是 27 个桶。
但是，27 个桶也少。
那么星耀二到星耀一还需要五颗星、青铜三到青铜二要三颗星才行呢。
这样算下来，就是 160 个桶。
160 个桶还是不够？
额。。。
推翻重来，直接把段位加上各种其他条件换算成积分，然后按照积分来拆分：

这样，想怎么拆分数段都行、拆多细都行。
完美。
等等，真的完美吗？
你看我的积分范围，都划分的非常的均匀。
按照段位拆分，有些菜鸡选手，打了两把觉得没意思，骂骂咧咧的退出游戏，就一直留在了青铜段位。
所以青铜段位的选手肯定是远大于荣耀王者的。
所以，实际情况下，用户的落点其实并不是均匀的。
怎么办？
这个时候就需要进行数据分析，通过一系列的高数、概率、离散等知识去做个桶大小的预估。
啊，这玩意就超纲了啊。
那就告辞，收工。

技术之外的考虑

做一个排行榜好像是一个很简单的事情。
但是其实不然，特别是推荐类的排行榜，需要避免马太效应：

比如作者推荐榜单，被推荐到前面的作者，曝光度很高。即使输出质量下降，但是还是很容易获得更多的关注。
位于榜单尾部的作者就很没有参与感。
于是两极分化就出现了，马太效应就来了。
对于这种情况怎么处理呢？
里面就涉及到一个复杂的计算公式了，比如掘金社区的掘力值，用于消息流推荐和作者榜单：
https://juejin.cn/book/6844733795329900551/section/6844733795380232206

所以千万不要错误的以为排行榜是一个非常简单的需求，这里面涉及到一些非常复杂的算法。

作者：why技术
链接：https://juejin.cn/post/6935021544372437029

ZSet多字段排序

zset只能根据score进行排序，也就是单字段排序。但是很多时候排序的规则不止一条，例如闯关排行榜不仅比较闯关成功的次数，还会比较通关的时长，复活的次数等等。这就导致了zset的字段远远不够用，那应该怎么同时使用多条排序规则呢？接下来就是需要使用取巧的办法了。

既然只有一个排序字段，那么根据排序规则的权重重新组合这个数值。通过把权重高的数值放在组合数的最前面来达到数值比较上的优势，说起来有点绕口，直接上例子吧。
场景如下：游戏闯关排行榜以通关次数正序、复活次数倒序和第一次通关的时间倒序来进行排序。
具体化数值：闯关5次、复活2次和第一次通关时间2020-06-09
那么score的数值的处理如下：

1. 闯关次数权重最高，所以5放在最前面
2. 复活次数倒序，则需要取反。在取反之前，需要确定复活的最大次数，例如99次，那么取反之后得到97
3. 通关时间倒序，也需要取反。先获取通关时间的时间戳，得到1591632000000。由于double位数限制，去掉最后毫秒数即最后三位，获取1591632000共十位，倒序则需要用最大数9999999999（10个9）减去当前值得8408367999

最终score=’5’+’97’+’8408367999’= 5978408367999 共13位数。显然通关次数小于5次的时候，score必然不能超过**5978408367999。**
这个方法需要注意的点就是zset的score字段是double类型。在double类型中的数值类型，需要注意整数的精度和小数点精度。double能保存最多16位的数字,如果复合排序字段中有时间的话,用于其他字段排序的数字只有6位,这就是复合数值排序的限制之处。

Redis数据备份

redis数据库属于内存性数据库，虽然速度快，也有持久化策略来保障高可用。但是大量的数据需要设置过期时间来腾出内存空间，所以需要通过定时任务将数据落到数据库中来保证数据，同时可以方便导出这些数据。实现起来也比较简单，通过当前所属周获取到redis的数据，对位落库就可以。
需要注意的就是定时任务的时间节点。为了保证本周的数据落库是最完整的数据，需要在下一周的第一次同步时再进行一次备份。这个时候就可以通过在redis中设置一个标志位，每次更新前判断是有上周数据已经同步的标志。

利用堆求 TopK 问题及其应用案例解决思路

利用堆求 TopK

堆的一个非常重要和经典的应用场景，那就是“求 Top K 问题”。
我把这种求 Top K 的问题抽象成两类。一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。另一类是针对动态数据集合，也就是说数据集合事先并不确定，有数据动态地加入到集合中。

针对静态数据，如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？

我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。 遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK)。

针对动态数据求得 Top K 就是实时 Top K，怎么理解呢？

举一个例子：一个数据集合中有两个操作，一个是添加数据，另一个询问当前的前 K 大数据。 如果每次询问前 K 大数据，都是基于当前的数据重新计算的话，那时间复杂度就是 O(nlogK)，n 表示当前的数据的大小。
实际上，我们可以一直都维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶 元素小，则不做处理。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以实时返回。

TopK 应用案例

案例说明

了解了上面堆的一些应用场景的处理思路之后，再来看下这个问题：假设现在有一个包含 10 亿个搜索关键词的日志文件，如何快速获取到 Top10 最热门的搜索关键词呢？
解决此问题，可以有很多相对比较高级的解决方法，比如使用 MapReduce 等。现在要求将处理的场景限定为单个机器，可使用的内存限定为 1GB，则此问题该如何解决呢？
首先因为用户搜索的是关键词，应该有很多可能都是重复的，所以首先想到的是要统计每个搜索关键词出现的频率，然后可以通过散列表、平衡二叉查找树或者其他一些支持快速查找、插入的数据结构，来记录关键词及其出现的次数。

选用散列表，解决思路及不足之处

假定选用散列表，解决思路如下：

1. 就顺序扫描这 10 亿个搜索关键词，每扫描到某个关键词时，就去散列表中查询；
2. 如果存在，则将对应的关键词的次数加一；如果不存在，就将它插入到散列表，并记录次数为 1；
3. 以此类推，等遍历完这 10 亿个搜索关键词之后，散列表中就存储了不重复的搜索关键词以及出现的次数。
4. 然后，再根据前面讲的用堆求 Top K 的方法，建立一个大小为 10 的小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现的次数；
5. 然后与堆顶的搜索关键词对比，如果出现次数比堆顶搜索关键词的次数多，那就删除堆顶的关键词，将这个出现次数更多的关键词加入到堆中；
6. 以此类推，当遍历完整个散列表中的搜索关键词之后，堆中的搜索关键词就是出现次数最多的 Top 10 搜索关键词了。

回过头分析下，上面的解决思路其实是不严谨的，或者说是存在漏洞的。怎么说呢，10 亿的关键词还是很多的，假设 10 亿条搜索关键词中不重复的有 1 亿条，如果每个搜索关键词的平均长度是 50 个字节，那存储 1 亿个关键词大概需要 5GB 的内存空间，而散列表由于需要避免频繁冲突，不会选择太大的装载因子，所以消耗的内存空间可能就更多了。而机器的可用内存空间只有 1GB，所以是无法一次性将所有的搜索关键词加入到内存中的。这个时候该做怎样的优化呢？

哈希算法 + 散列表 + 堆 实现获取 Top10 最热门搜索关键词的思路

哈希算法就派上用场了，相同数据经过哈希算法得到的哈希值是一样的。根据哈希算法的这一特点，可以先将 10 亿条搜索关键词通过哈希算法分片到 10 个文 件中。具体实现流程如下：

1. 创建 10 个空文件 00，01，02，……，09；
2. 遍历这 10 亿个关键词，并且通过某个哈希算法对其求哈希值；
3. 然后哈希值跟 10 取模，得到的结果就是这个搜索关键词应该被分到的文件编号。
4. 对这 10 亿个关键词分片之后，每个文件大概有 1 亿的关键词，去除掉重复的，可能也就只有 1000 万个左右，每个关键词平均 50 个字节，所以总的大小就是 500MB，所以 1GB 的内存完全可以放得下；
5. 针对每个包含 1 亿条搜索关键词的文件，利用散列表和堆，分别求出 Top 10；
6. 最后把这个 10 个 Top 10 放在一块，取这 100 个关键词中出现次数最多的 10 个即可。

Top N 解决方案

全部排序

直接对所有数据进行排序（快排等），缺点是需要将数据一次性加载到内存中。

局部淘汰

内存中维护一个大小为 N 的容器，再让剩余的数一个个进入容器，并淘汰容器内的最小值。最终容器内剩下的数就是前 N 名。优点是能节省内存，缺点是太慢了。

分治

把数据分为多个小组，小组内先分别选出前 N 名小组长，最后再让这些小组长同台竞技，选出最终的前 N 名。

哈希预处理

假如数据重复度很高，可以通过 hash 的方式，去掉很多重复数据。比如 1 亿个数据里，一半是 0，一半是 1，那么取前 10 名时，可以直接淘汰掉另一半为 0 的数据。

但是预处理本身也需要时间和空间，这就需要我们对数据的重复度有一个清晰的判断，否则自作聪明、适得其反。

小根堆

面试算法中的高频考点 —— 堆排序，可以先取前 N 个数组成小根堆，堆顶始终是最小值。 然后遍历后续数字，大于堆顶就替换掉堆顶并调整最小堆结构。该算法时间复杂度和空间复杂度（为 N，常数）都不错，所以必须要掌握。
但是具体选择哪种方案呢？还是要结合我们实际的项目和业务场景来分析。

利用分布式思想处理海量数据

面对海量数据，我们就可以放分布式的方向去思考了
我们可以将数据分散在多台机器中，然后每台机器并行计算各自的 TopK 数据，最后汇总，再计算得到最终的 TopK 数据，这种数据分片的分布式思想在面试中非常值得一提，在实际项目中也十分常见

利用最经典的方法，一台机器也能处理海量数据

其实提到 Top K 问题，最经典的解法还是利用堆。
维护一个大小为 K 的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。
当然，如果是求前 K 个最小的数，只需要改为大顶堆即可

将数据插入堆

95 大于 20，进行替换

95 下沉，维持小顶堆

对于海量数据，我们不需要一次性将全部数据取出来，可以一次只取一部分，因为我们只需要将数据一个个拿来与堆顶比较。
另外还有一个优势就是对于动态数组，我们可以一直都维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就直接拿它与堆顶的元素对比。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以里立刻返回给他。
整个操作中，遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK)，加起来就是 O(nlogK) 的复杂度，换个角度来看，如果 K 远小于 n 的话， O(nlogK) 其实就接近于 O(n) 了，甚至会更快，因此也是十分高效
最后，对于 Java，我们可以直接使用优先队列 PriorityQueue 来实现一个小顶堆，这里给个代码：

public List<Integer> solutionByHeap(int[] input, int k) {
    List<Integer> list = new ArrayList<>();
    if (k > input.length || k == 0) {
        return list;
    }
    Queue<Integer> queue = new PriorityQueue<>();
    for (int num : input) {
        if (queue.size() < k) {
            queue.add(num);
        } else if (queue.peek() < num){
            queue.poll();
            queue.add(num);
        }
    }
    while (k-- > 0) {
        list.add(queue.poll());
    }
    return list;
}

实际解决

由于我们的数据库来记录积分，所以当用户量级很大时，首先要 分库分表 ，通常是水平分表，根据一定规则（比如 id）把用户数据行分批存储在多个数据表中。

然后就和大数据 Map / Reduce 处理机制一样了，可以采用 分治 的方式 并行计算 每个表的前 10 名（map），都计算好后，再汇总到一起计算最终的前 10 名（reduce）。

用这种方式，别说 1 亿了，2 亿、3 亿的计算模式都是一样的，加机器水平扩容就好了~

所以遇到 Top N 问题的时候，大家可以先答一下上面的几种方案，再结合具体的场景分析，分治和最小堆是我觉得相对 核心 的点。

Redis

最后，对于实时排行榜的设计，肯定很多背过八股文面试题的朋友在第一时间会想到使用 Redis 的有序集合 zset，的确也是一种方案，但也要结合场景去分析利弊，不要秒答。

使用基于内存的 Redis zset 的确运算更快，且天然支持排序、使用方便。但数据量大时同样面临数据更新、维护、同步、持久化存储等问题，而且对于我们这种实时性要求不高的需求来说，有些大材小用了哈哈。
[

](https://blog.csdn.net/weixin_41701290/article/details/118313087)