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

OPTIMIZED R TREE BUFFER MANAGEMENT ALGORITHM AND ITS EVALUATION

在分析Ｒ－树操作特性和ＬＲＵ算法的基础上，提出了一种新的基于ＬＲＵ的Ｒ－树缓冲管理算法ＰＩＮ－ＬＲＵ．该算法对Ｒ－树访问路径上的节点进行标记，动态地在缓冲区中将访问路径上的节点加“钉”和释放“钉”，从面尽可能减少不必要的内－外存数据交换，提高Ｒ－树缓冲管理的效率．实验表明，ＰＩＮ－ＬＲＵ算法在磁盘Ｉ／Ｏ和页面访问命中率等方面均优于ＬＲＵ算法．

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.