计算机技术与发展
計算機技術與髮展
계산궤기술여발전
COMPUTER TECHNOLOGY AND DEVELOPMENT
2015年
5期
60-63
,共4页
倒排索引%缓存替代策略%爱憎算法%LRU和MRU算法
倒排索引%緩存替代策略%愛憎算法%LRU和MRU算法
도배색인%완존체대책략%애증산법%LRU화MRU산법
inverted index%cache replacement strategy%love and hate algorithm%LRU and MRU algorithm
为提高倒排索引的构建速度和检索效率，设计与实现了一套专门的缓存系统。整个缓存系统包含一个用于跟踪每个缓存帧状态的缓存帧描述器BufDesc和一张用于将文件及页号映射到缓存池帧号的动态哈希表BufHashTable。缓存帧描述器记录该缓存页是否被修改过、该缓存页是否可用以及该缓存页是否为有效页等信息，它通过双向链表将所有BufDesc类的实例链接在一起。缓存替代策略使用爱憎算法，即采用给帧加Love/Hate标记的方式选择被替代出去的页，它是对传统LRU和MRU算法的改进，能显著提升倒排索引的性能。
為提高倒排索引的構建速度和檢索效率，設計與實現瞭一套專門的緩存繫統。整箇緩存繫統包含一箇用于跟蹤每箇緩存幀狀態的緩存幀描述器BufDesc和一張用于將文件及頁號映射到緩存池幀號的動態哈希錶BufHashTable。緩存幀描述器記錄該緩存頁是否被脩改過、該緩存頁是否可用以及該緩存頁是否為有效頁等信息，它通過雙嚮鏈錶將所有BufDesc類的實例鏈接在一起。緩存替代策略使用愛憎算法，即採用給幀加Love/Hate標記的方式選擇被替代齣去的頁，它是對傳統LRU和MRU算法的改進，能顯著提升倒排索引的性能。
위제고도배색인적구건속도화검색효솔，설계여실현료일투전문적완존계통。정개완존계통포함일개용우근종매개완존정상태적완존정묘술기BufDesc화일장용우장문건급혈호영사도완존지정호적동태합희표BufHashTable。완존정묘술기기록해완존혈시부피수개과、해완존혈시부가용이급해완존혈시부위유효혈등신식，타통과쌍향련표장소유BufDesc류적실례련접재일기。완존체대책략사용애증산법，즉채용급정가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.
