优化的R-树缓冲管理算法  

OPTIMIZED R TREE BUFFER MANAGEMENT ALGORITHM AND ITS EVALUATION

作　　者：陈晟[1] 景宁[1] 孙茂印[1] 

机构地区：[1]国防科学技术大学电子工程学院

出　　处：《计算机学报》1999年第5期496-501,共6页Chinese Journal of Computers

基　　金："八五"国防预研基金;国防科学技术大学基金

摘　　要：在分析Ｒ－树操作特性和ＬＲＵ算法的基础上，提出了一种新的基于ＬＲＵ的Ｒ－树缓冲管理算法ＰＩＮ－ＬＲＵ．该算法对Ｒ－树访问路径上的节点进行标记，动态地在缓冲区中将访问路径上的节点加“钉”和释放“钉”，从面尽可能减少不必要的内－外存数据交换，提高Ｒ－树缓冲管理的效率．实验表明，ＰＩＮ－ＬＲＵ算法在磁盘Ｉ／Ｏ和页面访问命中率等方面均优于ＬＲＵ算法．Based on widely used LRU algorithm and characteristics of R tree operations, this paper proposes an optimized R tree buffer management algorithm PIN LRU. This algorithm pins the node on the access path in the cache when retrieving the R tree downwards from root to leaf, and releases the ‘pin’ when retrieving the same node upwards. The pin guarantees nodes in access path not be swapped out of the cache before the retrieval process access them upwards. In buffer management aspect, some pages are kept in cache, which are expected to be referenced in the near future, to avoid local memory thrashing. This algorithm takes the advantage of data structure and characteristics to improve the efficiency of R tree operations. The experimental result shows that PIN LRU has better performance than LRU in both disk I/O and page fault.

关 键 词：R-树 缓冲管理 LRU算法 数据结构 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]