设计数据访问策略

百度的面试题一道：

 

在处理磁盘数据时，需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中，则可以直接访问内存。通常来说内存是有限的，因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据，内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求，要求它们必须按照给定的顺序被读取，同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。

 

解析：目标是最小化磁盘读取次数，分两部分：

 

内存中的m块数据按照LRU策略组织，由于已经给出了读取请求，或许可以进一步提高swap的效率，

磁盘上数据用B树或者其变种实现，最小化磁盘读取。