算术

有一套40G的数据，其中的每条数据都是一个键值对，所有的键都是唯一的。给你一台计算机，只有1G的内存，请设计一个方案如何才能有效的通过键来访问对应的值。请最小化内存的页面失效请求。

我的答案：

问题的关键是如何建立有效的索引。当操作系统从磁盘加载数据，一般为一个页面大小。为了降低页面请求的次数，我们必须每次尽可能的充分使用这一页面中的数据。 

为了说明方便，我假设页面大小为4K，每个键是一个4字节整数，共有1G个不同的键。索引中除了需要保存键本身外，还需要保存一个4字节的偏移量用于指出数据或者下一级索引的位置。

所以一个页面最多能够容纳512个索引条目。我们总共需要1G个索引条目，因而需要4 (512^4 > 1G)级索引。上级索引中的每一个条目对应着下级索引的512个条目。每一级索引包括512个条目（即一个页面大小），加载到内存之后可以使用二分查找来确定下一级索引的位置。为了定位具体一个键对应的数据的位置，我们最多需要从磁盘中加载4个索引即可，因而只需要最多4次页面请求。