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

Research and Implementation of an Inverted Index Cache Replacement Algorithm

作　　者：时亚南 束文杰 

机构地区：[1]新疆维吾尔自治区特种设备检验研究院,新疆乌鲁木齐830011

出　　处：《计算机技术与发展》2015年第5期60-63,共4页Computer Technology and Development

基　　金：新疆维吾尔自治区科技攻关项目(200931103)

摘　　要：为提高倒排索引的构建速度和检索效率,设计与实现了一套专门的缓存系统。整个缓存系统包含一个用于跟踪每个缓存帧状态的缓存帧描述器Buf Desc和一张用于将文件及页号映射到缓存池帧号的动态哈希表Buf Hash Table。缓存帧描述器记录该缓存页是否被修改过、该缓存页是否可用以及该缓存页是否为有效页等信息,它通过双向链表将所有Buf Desc类的实例链接在一起。缓存替代策略使用爱憎算法,即采用给帧加Love/Hate标记的方式选择被替代出去的页,它是对传统LRU和MRU算法的改进,能显著提升倒排索引的性能。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.

关 键 词：倒排索引 缓存替代策略 爱憎算法 LRU和MRU算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]