想一下数据库索引怎么做的? 参考b树的实现.

对这题来说, 10亿在 G量级, 分成100份, 为10M量级, 基本上放入内存无压力了.

在这10亿记录中, 均分为100份, 把每份的 第一条记录关键字和 此记录对应的文件偏移量先 扫入内存(类似索引?), 这里需要 磁盘随机io 100次.

这样可以马上定位出 指定关键字所在的记录块, 把相应的记录块拿到内存, 二分查找即可.

更新

数据库定位, 上面的这一点点还差很多啊...

数据库一般:
1). 全表扫描, 没啥好说的;
2). b树索引, 拿oracle来说, 索引的叶节点 存的有 (记录的索引键值, 记录的rowid)
rowid为10个bytes, 存有 segment,file, block, row in the block. 这样可以通过rowid直接找到此记录的物理地址.
详见:
http://www.dbms-notes.com/2010/12/ora...

更多索引知识, 参见:
http://www.orafaq.com/node/1403