一种树链双访表结构的快速查找算法  

A Quick Search Algorithm Based on Tree&Chain Dual Access Table

作　　者：韩永 姚念民[1] 蔡绍滨[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001

出　　处：《小型微型计算机系统》2013年第7期1558-1562,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61073047)资助;中央高校基本科研业务费专项项目(HEUCFT1202)资助

摘　　要：查找是计算机应用中的常用基本运算.当前有很多查找算法针对关键字的查找概率问题进行了优化.处理器对高速缓存和主存的访问存在着巨大的速度差异.因此,随着高缓技术的快速发展及其容量的扩大,提高访问概率较高关键字的高缓命中率成为加速查找的一个重要因素.提出一种能够根据关键字的访问统计自适应调整的树链双访表结构.该算法能适应访问数据的分布特点,在应用中动态统计关键字访问次数,提高访问概率较高关键字的高缓命中率,从而实现快速查找.实验表明,随着测试集中热关键字查找比率的增大,树链双访表查找算法的性能优势也越明显.Searching is a commonly basic operation in computer applications.Currently many searching algorithms are optimized according to the searching probability of keys.There are enormous processor access speed disparities betw een the cache and the main memory.Therefore,w ith the rapid development of the cache technology and the expansion of its capacity,improving the percentage of cache hits of the keyw ords w ith high access probability becomes an important factor of search acceleration.A TreeChain dual access table is presented,and it can make adjustments adaptively according to the access statistical of the keyw ords.The proposed algorithm can adapt to the distributed characteristic of access data and dynamically count the access of the keyw ords in practical application,and so it improves the cache hits of the keyw ords w ith high access probability,thereby realizing the fast search.The experimental result indicates that,w ith the increasing of the searching probability of hot keys in the test sets,the performance advantage of the TreeChain table searching algorithm becomes more remarkable.

关 键 词：高速缓存 数据查找 访问统计 自适应 树链结构 

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