迅雷的一个面试题

假如有这样一个数据源

id

scores

一共2亿条记录，其中分数已经是排好了序的。

 

要求用户登录就显示用户分数在用户中的排名。

 

想了5分钟我的方案是：首先分库，跨度分成10个表，每个表的数据量大体相等。

 

再记录对应的分数阶段，如：第一张表0-1000分，约有1000w用户，第二张1000-1800分，约1000w。。。。。。。。。。。。

 

用lucene 给10张表做索引，保存索引文件，用户上来通过lucene 找到分数，找到对应数据库。

 

这是面试官来了一句，内存只有1G，也就是说我不能1次加载出1000w用户的分数出来，做二分查找。（我想他是这意思，至于是不是这意思，不管你信不信。。此处省略500字。。。）

 

然后我支支吾吾，不知道说了什么，

 

最好面试官说，你思维混乱，out！

 

回来想了很久没相同，怎么把这10000w加载出来，希望大家给个思路，谢谢

 

 

感谢大家的回答，这个问题确实很开放，解决思路一定很多，这个同学总结的很优雅，当然还有更多，更好的。权当参考http://www.cnblogs.com/weidagang2046/archive/2012/03/01/massive-user-ranking.html

 

 

这样怎么样？
存储部分排名信息，第1,1*n,2*n,3*n,...的排名信息（分数）
1亿用户平均抽取n = 1亿/(k=10000) = 10000
即内存中存储了平均分布在排名中的10000个用户的排名信息（定时同步内存与数据的对应排名用户信息）

通过二分差找确认用户所属分区，
读取分区内容，再通过二分查找获得具体排名

分库？

分区就行吧


2亿也没多大 我处理过10E的数据量 分区加索引就搞定

哦，那拿出来共享下嘛，我这方面不是太懂了，谢谢了

不错，我试试，谢谢啦

select count(*) from rank where score < 分数

有索引的话，在2亿条数据下，不知道效率怎么样


很实际的一个问题，之前我登陆迅雷个人中心的时候，就能看到我的迅雷账号在全球排多少位。

我感觉这个没什么难的啊，有两个方法

1.用数据库的话，采用分表的策略，每个表里的数据肯定知道吧，查看在哪个表里，计算偏移量，数量除以总数，就是结果。
2.如果自己存储数据结构话，scores采用10层的跳表顺序存储，scores与scores采用差值算法压缩存储量，这样一个一个遍历，计算出是第几个，然后除以总数

select count(1) from tableName where scores>(select scores from tableName where id=MyID)

能不能说的具体点

假设：
分区：1              2           3            4        5。。。
分数：[0, 1000),[1000, 2000),[2000, 3000),[3000, 4000),[)。。。

分别给id、score加索引，用户一登录，就知道id,通过id查找score，即可知道该score所在的分区，如score=2300，位于分区3.

通过select计算3以后的比2300大的共有多少个，可以通过分数范围，一个分区一个分区地求，最后累加的结果再加1就是该用户的排名。
---------------
允许扔XX，但请手下留情