3000w数据的表，取某项字段前50项数据 ，内存2g

偶然看到这个题，就想了一下怎么做，大体实现思路是这样子的，3000w的数据划分为1000段，也就是1-3w为一段，30001-6w项为第二段，依次类推，从每3w的数据中提取出前50条数据（这个根据sql排序就能取出来，2个g的内存够了），最后1000个50就会产生5w个数据，最后提取出来的5w的数据放置到ArrayList中去，最后5w的数据统一排序，取出前50条。5w*5w的对比与交换是可以搞定的。具体实现，等最近的项目完了 用多线程试试！~

评论

13 楼 sky726 2009-10-02  

恕我愚昧，不是很清楚题目意思
“取某项字段前50项数据”

比如这字段全部都是数字(1~3000w升序)
那题目做出来的结果，是不是1~50？
如果是这样，那分段来做结果怎么会对呢？

12 楼 wang_scu 2009-10-02  

应该是map/reduce模型　每个map记录最大的50个数（省了所有排序比较），最后一个reduce找前面所有最大的50个数。不知道可不可以。

11 楼 lnaigg 2009-10-02  

我想的：
a. 3000w数据，分成3000组，每组1000条。分组不用占内存，前提是数据是顺序数据。
b. 每组数据找出最大值，并记录该组ID。找最大值的算法只需要1K内存，存各族最大值及组ID是3K内存。
c. 对各组的最大值进行排序，找出前50组ID。3K数据排序，内存需求也不高。
d. 排序前50组数据，总共就剩下5万条了，直接排序即可。
e. 5万条数据也可以再按之前方法细分一次。

10 楼 J-catTeam 2009-10-01  

minimu 写道

原体的描述是什么样子的呢？

就是上面样子的····

9 楼 minimu 2009-10-01  

原体的描述是什么样子的呢？

8 楼 J-catTeam 2009-10-01  

b5158488 写道

这是阿里巴巴最后的压轴题吧

嘿嘿 是的

7 楼 J-catTeam 2009-10-01  

xinggm 写道

也不知道该怎么回答你，阿里巴巴一面要求不要泄题，另一面网上又有人要来讨论，这个题，楼主把我的意思理解错了，3000W的数据要在内存中解决，不能放在数据库中，否则，它还要你写什么算法呀。直接分表不就得了，这是在DBA要解决的问题，不是程序员的事情了。

3000w的数据 放不下啊~！2g的内存

6 楼 xinggm 2009-10-01  

也不知道该怎么回答你，阿里巴巴一面要求不要泄题，另一面网上又有人要来讨论，这个题，楼主把我的意思理解错了，3000W的数据要在内存中解决，不能放在数据库中，否则，它还要你写什么算法呀。直接分表不就得了，这是在DBA要解决的问题，不是程序员的事情了。

5 楼 b5158488 2009-10-01  

这是阿里巴巴最后的压轴题吧

4 楼 mwmw 2009-10-01  

3000w的表的话，如果要排序的那一列可以做index的话，做个index就好了，如果能做cluster index（SQLServer的功能）做个cluster index，select 一下也不会很慢的。 如果不能做这种index的话排序也没有意义的（但是仍然可以用fulltext search）

ps: 3000w级别的表还好，如果再大上一两个数量级，我就没有见过了。

3 楼 J-catTeam 2009-10-01  

kimmking 写道

按排序字段做多级索引

可以具体点么？
我对这个小看了
~~

2 楼 kimmking 2009-10-01  

按排序字段做多级索引

1 楼 J-catTeam 2009-10-01  

想了一下，5w的数据放在int数组里用Arrays.sort()方法排下来就可以了。