存储结构首先我们用一张用户积分表user_score来保存用户的积分信息。表结构示例数据下面的算法会基于这个基本的表结构来进行。算法1简单SQL查询首先我们很容易想到用一条简单的SQL语句查询出积分大于该用户积分的用户数量select 1 count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid uid and t2.score t1.score对于4号用户我们可以得到下面的结果算法特点优点简单利用了SQL的功能不需要复杂的查询逻辑也不引入额外的存储结构对小规模或性能要求不高的应用不失为一种良好的解决方案。缺点需要对user_score表进行全表扫描还需要考虑到查询的同时若有积分更新会对表造成锁定在海量数据规模和高并发的应用中性能是无法接受的。算法2均匀分区设计在许多应用中缓存是解决性能问题的重要途径我们自然会想能不能把用户排名用Memcached缓存下来呢不过再一想发现缓存似乎帮不上什么忙因为用户排名是一个全局性的统计性指标而并非用户的私有属性其他用户的积分变化可能会马上影响到本用户的排名。然而真实的应用中积分的变化其实也是有一定规律的通常一个用户的积分不会突然暴增暴减一般用户总是要在低分区混迹很长一段时间才会慢慢升入高分区也就是说用户积分的分布总体说来是有区段的我们进一步注意到高分区用户积分的细微变化其实对低分段用户的排名影响不大。于是我们可以想到按积分区段进行统计的方法引入一张分区积分表score_range表结构数据示例表示[from_score, to_score)区间有count个用户。若我们按每1000分划分一个区间则有[0, 1000), [1000, 2000), …, [999000, 1000000)这1000个区间以后对用户积分的更新要相应地更新score_range表的区间值。在分区积分表的辅助下查询积分为s的用户的排名可以首先确定其所属区间把高于s的积分区间的count值累加然后再查询出该用户在本区间内的排名二者相加即可获得用户的排名。乍一看这个方法貌似通过区间聚合减少了查询计算量实则不然。最大的问题在于如何查询用户在本区间内的排名呢如果是在算法1中的SQL中加上积分条件select 1 count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid uid and t2.score t1.score and t2.score to_score在理想情况下由于把t2.score的范围限制在了1000以内如果对score字段建立索引我们期望本条SQL语句将通过索引大大减少扫描的user_score表的行数。不过真实情况并非如此t2.score的范围在1000以内并不意味着该区间内的用户数也是1000因为这里有积分相同的情况存在二八定律告诉我们前20%的低分区往往集中了80%的用户这就是说对于大量低分区用户进行区间内排名查询的性能远不及对少数的高分区用户所以在一般情况下这种分区方法不会带来实质性的性能提升。算法特点优点注意到了积分区间的存在并通过预先聚合消除查询的全表扫描。缺点积分非均匀分布的特点使得性能提升并不理想。算法3树形分区设计均匀分区查询算法的失败是由于积分分布的非均匀性那么我们自然就会想能不能按二八定律把score_range表设计为非均匀区间呢比如把低分区划密集一点10分一个区间然后逐渐变成100分1000分10000分 … 当然这不失为一种方法不过这种分法有一定的随意性不容易把握好而且整个系统的积分分布会随着使用而逐渐发生变化最初的较好的分区方法可能会变得不适应未来的情况了。我们希望找到一种分区方法既可以适应积分非均匀性又可以适应系统积分分布的变化这就是树形分区。我们可以把[0, 1,000,000)作为一级区间再把一级区间分为两个2级区间[0, 500,000), [500,000, 1,000,000)然后把二级区间二分为4个3级区间[0, 250,000), [250,000, 500,000), [500,000, 750,000), [750,000, 1,000,000)依此类推最终我们会得到1,000,000个21级区间[0,1), [1,2) … [999,999, 1,000,000)。这实际上是把区间组织成了一种平衡二叉树结构根结点代表一级区间每个非叶子结点有两个子结点左子结点代表低分区间右子结点代表高分区间。树形分区结构需要在更新时保持一种不变量(Invariant)非叶子结点的count值总是等于其左右子结点的count值之和。以后每次用户积分有变化所需要更新的区间数量和积分变化量有关系积分变化越小更新的区间层次越低。总体上每次所需要更新的区间数量是用户积分变量的log(n)级别的也就是说如果用户积分一次变化在百万级更新区间的数量在二十这个级别。在这种树形分区积分表的辅助下查询积分为s的用户排名实际上是一个在区间树上由上至下、由粗到细一步步明确s所在位置的过程。比如对于积分499,000我们用一个初值为0的排名变量来做累加首先它属于1级区间的左子树[0, 500,000)那么该用户排名应该在右子树[500,000, 1,000,000)的用户数count之后我们把该count值累加到该用户排名变量进入下一级区间其次它属于3级区间的[250,000, 500,000)这是2级区间的右子树所以不用累加count到排名变量直接进入下一级区间再次它属于4级区间的…直到最后我们把用户积分精确定位在21级区间[499,000, 499,001)整个累加过程完成得出排名虽然本算法的更新和查询都涉及到若干个操作但如果我们为区间的from_score和to_score建立索引这些操作都是基于键的查询和更新不会产生表扫描因此效率更高。另外本算法并不依赖于关系数据模型和SQL运算可以轻易地改造为NoSQL等其他存储方式而基于键的操作也很容易引入缓存机制进一步优化性能。进一步我们可以估算一下树形区间的数目大约为2,000,000考虑每个结点的大小整个结构只占用几十M空间。所以我们完全可以在内存建立区间树结构并通过user_score表在O(n)的时间内初始化区间树然后排名的查询和更新操作都可以在内存进行。一般来讲同样的算法从数据库到内存算法的性能提升常常可以达到10^5以上因此本算法可以达到非常高的性能。算法特点优点结构稳定不受积分分布影响每次查询或更新的复杂度为积分最大值的O(log(n))级别且与用户规模无关可以应对海量规模不依赖于SQL容易改造为NoSQL或内存数据结构。缺点算法相对更复杂。算法4积分排名数组算法3虽然性能较高达到了积分变化的O(log(n))的复杂度但是实现上比较复杂。另外O(log(n))的复杂度只在n特别大的时候才显出它的优势而实际应用中积分的变化情况往往不会太大这时和O(n)的算法相比往往没有明显的优势甚至可能更慢。考虑到这一情况仔细观察一下积分变化对排名的具体影响可以发现某用户的积分从s变为sn积分小于s或者大于等于sn的其他用户排名实际上并不会受到影响只有积分在[s,sn)区间内的用户排名会下降1位。我们可以用于一个大小为1,000,000的数组表示积分和排名的对应关系其中rank[s]表示积分s所对应的排名。初始化时rank数组可以由user_score表在O(n)的复杂度内计算而来。用户排名的查询和更新基于这个数组来进行。查询积分s所对应的排名直接返回rank[s]即可复杂度为O(1)当用户积分从s变为sn只需要把rank[s]到rank[sn-1]这n个元素的值增加1即可复杂度为O(n)。算法特点优点积分排名数组比区间树更简单易于实现排名查询复杂度为O(1)排名更新复杂度O(n)在积分变化不大的情况下非常高效。缺点当n比较大时需要更新大量元素效率不如算法3。总结