求内存高效的排名变更追踪算法：赛车游戏高分榜批量更新

现有高分表示例 #

Rank列规则 #

Rank列预计算生成，遵循ORDER BY Time, Datetime排序规则；每个玩家仅保留最优成绩的有效排名，null排名的记录为玩家非最优成绩，仅用于历史图表展示。

现有排名更新方案 #

插入新高分时，有两种更新方式：

• 批量失效+定期全量更新：插入新行并标记旧排名失效，定期全表查询去重后，通过批量CASE WHEN语句统一更新所有排名。
• 单条变动实时更新：查询玩家旧排名→计算新排名→更新区间排名→插入新记录→标记旧记录失效。

后者曾因新关卡发布时大量最优成绩提交导致服务器负载过高；前者负载更低，但需要实现失效队列。由于数据库每次查询后会执行fsync，单查询多更新的效率远高于多查询操作，因此需要批量处理(oldrank, newrank)对。

算法需求 #

需要一种无需O(n)内存的算法，基于排名范围生成批量更新规则。例如当Bob从500名升至1名、Carol从350名升至100名时，生成如下范围更新指令：

• rank[1-99] +=1
• rank[100-349] +=2
• rank[351-499] +=1

当前技术栈为标准LAMP栈。

内容的提问来源于stack exchange，提问作者Luc