ranklist
游戏排行榜算法设计实现
- September 12, 2020
- mikzzz
需求背景:
查看前top N的排名用户
查看自己的排名
用户积分变更后,排名及时更新
方案一:MySQL来实现
利用MySQL来实现,存放一张用户积分表user_score
游戏排行榜算法设计实现比较
取前top N,自己的排名都可以通过简单的sql语句搞定。
算法简单,利用sql的功能,不需要其他复杂逻辑,对于数据量比较少、性能要求不高,可以使用。但是对于海量数据,性能是无法接受的。
方案二:skiplist的实现
用这个实现起来比较简单;用hashmap来存储具体的对象;用skiplist用来排序。也可以简单的用一个map和set来实现。Map内面存具体对象,set用来排序。
关于skip list这里简单介绍下:skip list是链表的一种特殊形式,对链表的一种优化;保证INSERT和REMOVE操作是O(logn),而通用链表的复杂度为O(n);
优点:实现较简单,效率基本上O(log(N))
缺点:当达到亿级别时的数据时,性能会急剧下降
方案三:基于redis的 sort set的实现
redis的zset用来做排行榜的、好友列表, 去重, 历史记录等业务需求。接口使用非常简单。接口非常丰富,基本上需要的实现都能满足,说明如下:
ZAdd/ZRem是O(log(N)),ZRangeByScore/ZRemRangeByScore是O(log(N)+M),N是Set大小,M是结果/操作元素的个数。
ZSET的实现用到了两个数据结构:hash table 和 skip list(跳跃表),其中hash table是具体使用redis中的dict来实现的,主要是为了保证查询效率为O(1) ,而skip list(跳跃表)主要是保证元素有序并能够保证INSERT和REMOVE操作是O(logn)的复杂度。
优点:基于redis开发,速度快;使用redis相关特性
缺点:当达到亿级别时的数据时,性能会急剧下降