用双向链表就可以解决这个问题,双向链表可以以O(1)的时间访问头尾元素。还有个问题,如果调用Insert(v),按照之前的算法,我先得知道v在不在这个双向链表中,如果不在直接插到头部,如果在的话,将其提取到头部。如果仅仅是双向链表,那么还是需要遍历一遍队列,查询v是不是已经在队列中了。
可以用一个map记录已经在队列中的元素到链表节点的键值对,这样就可以以O(1)的时间查询某个value是否已经在队列中。
最终确定数据结构如下:
假设两种极端的情况:
没有缓冲池,那么数据都位于磁盘上,第一次访问一页数据,需要将其从磁盘读取到内存,第二次在访问相同的页时,还需要从磁盘读,非常耗时。
假设内存无限大,那么访问一页数据后,将该页数据直接保存到内存,下次再访问该页时,直接访问内存缓存就行。但是现实中内存比磁盘容量小得多,只能缓存有限个数据页,如下图内存只能缓存三个页,依次访问PAGE 1, 2, 3, 现在已经缓存了PAGE 1, 2, 3,假设想读取PAGE 4,那么得先清空一个内存缓存页,用来缓存PAGE 4的数据,那么清除谁呢?。这时候任务2的替换策略就派上用场了,根据LRU替换策略,PAGE 1是最近最久没有被使用过的,那么就将PAGE 1重新写回到磁盘,然后将PAGE 4读取到内存。
所以BUFFER POOL MANAGER的作用是加速数据的访问,同时对使用者来说是透明的。
具体代码就不贴了,可以参考我的实现:https://github.com/gatsbyd/cmu_15445_2018