排行榜的设计

algorithm

排行榜这类功能应用场景非常的广，能够满足用户很多的欲望。下面就来看看几种实现思路。

所谓排行榜其基本的功能要包括：

• 能够获取 TOP N
• 能够获取指定对象的排名

DB

首先最简单的方法就是直接利用DB的力量，拿 MySql 为例，存储维护一张 key-score 的表，上述两个数据都可以使用 sql 简单查询获得。

这种方法的优点就是实现非常简单，没有任何复杂代码逻辑，在有对应索引的情况下查询性能也很好。不过有一个缺点就是毕竟是磁盘IO，当写非常频繁的时候，就需要一些措施来处理了，这和计数一个道理。

使用 DB 还有一个好处就是，当这个排名是多维度的时候，依赖 DB 将很容易处理这种情况，把表结构修改为 key-score-score 的形式，在 score 上建立联合索引，然后一条 order 就解决问题了。

积分排名 Map

如果要自己实现的话，一种简单的做法就是维护一份积分排名map，其结构：

arr[score] = ranking

因为是 map，故可以知道查询复杂度为 O(1)，更新这个 map 的时间复杂度为 O(n)。当有积分变化时，不需要更新整个 map ，只对变化区间内的 ranking 加一即可。

类似的也可以维护一个堆结构来实现。

Map + Skiplist

使用 map 可以保证在查询复杂度上保持高效的 O(1)，但维护顺序的效率却是不高。这个时候就可以引入 skip list 结构，使用它来高效的维护排序。

具体的 skip list 结构实现，我之前有一篇分享曾经讲过，有兴趣的可以看一下，这里就不多做介绍了：
数据结构之 skip list

这种结构能使插入删除的时间复杂度降低到对数级 O(logn)

这种方式其实你也不需要自己再去实现一番了，因为 redis 的 SortedSet 结构就是类似的实现，接下来就来看看用得最多的 SortedSet 实现法

Redis - SortedSet

SortedSet 结构我在之前也有做过分享：
浅谈 redisObject
Redis - Sorted Set

有现成的优秀轮子就方便的多了，你大致了解后就会发现 SortedSet 结构就是天生擅长做排行榜的轮子，系统集成也异常简单。

其几个操作的时间复杂度都可以保持在对数级
因为其内部使用 skiplist 来实现的，zadd 和 zrem 的时间复杂度为 O(logn)
而获取榜单 TOP n 的操作 zrangbyscore 及 zremrangbyscore 的时间复杂度也都保持在 O(logn + m) ，其中 n 为 set 的总大小，m 为返回集合的大小。

在百万千万级数据下，这种实现简单易操作同时性能也相当优异。不过当数据集过亿后我就不能保证其性能是否还能如此美丽了。
这个时候就可以考虑 hash 分堆了，使用分治的思路去处理将是个不错的祖选择，不过这已经超出本篇的介绍范围了，之后有机会我会单独开一篇来介绍这种方法。