一种倒排索引缓存替代算法的研究与实现

摘要

In order to improve the construction speed and retrieval efficiency of the inverted index,design and implement a set of special-ized caching system. The entire cache system includes a frame buffer descriptor BufDesc which is used to track the status of each cache frame and one for the file and page number that is mapped to a frame number of the dynamic buffer pool hash table BufHashTable. Frame buffer descriptor records whether the cached page has been modified,the cached page is available and whether the information is valid cached pages and so on,it adopts a doubly linked list of all the instances of the BufDesc class together. Love and hate algorithm is used as an alternative strategy that uses to frame plus Love/Hate marker selection that is an alternative way out of the page,which improves the traditional LRU and MRU algorithm,and can significantly improve the performance of the inverted index.%为提高倒排索引的构建速度和检索效率，设计与实现了一套专门的缓存系统。整个缓存系统包含一个用于跟踪每个缓存帧状态的缓存帧描述器BufDesc和一张用于将文件及页号映射到缓存池帧号的动态哈希表BufHashTable。缓存帧描述器记录该缓存页是否被修改过、该缓存页是否可用以及该缓存页是否为有效页等信息，它通过双向链表将所有BufDesc类的实例链接在一起。缓存替代策略使用爱憎算法，即采用给帧加Love/Hate标记的方式选择被替代出去的页，它是对传统LRU和MRU算法的改进，能显著提升倒排索引的性能。