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

摘要：

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

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

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2015-06-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：60-63