CMU-15445 LAB1:Extendible Hash Table, LRU, BUFFER POOL MANAGER (2)

用双向链表就可以解决这个问题,双向链表可以以O(1)的时间访问头尾元素。还有个问题,如果调用Insert(v),按照之前的算法,我先得知道v在不在这个双向链表中,如果不在直接插到头部,如果在的话,将其提取到头部。如果仅仅是双向链表,那么还是需要遍历一遍队列,查询v是不是已经在队列中了。

可以用一个map记录已经在队列中的元素到链表节点的键值对,这样就可以以O(1)的时间查询某个value是否已经在队列中。
最终确定数据结构如下:

3_lab1_LRU_data_structure

BUFFER POOL MANAGER 为什么需要BUFFER POOL MANAGER

假设两种极端的情况:

没有缓冲池,那么数据都位于磁盘上,第一次访问一页数据,需要将其从磁盘读取到内存,第二次在访问相同的页时,还需要从磁盘读,非常耗时。

假设内存无限大,那么访问一页数据后,将该页数据直接保存到内存,下次再访问该页时,直接访问内存缓存就行。但是现实中内存比磁盘容量小得多,只能缓存有限个数据页,如下图内存只能缓存三个页,依次访问PAGE 1, 2, 3, 现在已经缓存了PAGE 1, 2, 3,假设想读取PAGE 4,那么得先清空一个内存缓存页,用来缓存PAGE 4的数据,那么清除谁呢?。这时候任务2的替换策略就派上用场了,根据LRU替换策略,PAGE 1是最近最久没有被使用过的,那么就将PAGE 1重新写回到磁盘,然后将PAGE 4读取到内存。

4_lab1_buffer_pool

所以BUFFER POOL MANAGER的作用是加速数据的访问,同时对使用者来说是透明的。

具体代码就不贴了,可以参考我的实现:https://github.com/gatsbyd/cmu_15445_2018

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyxpjy.html