Buffering of index structure

摘要

Buffering of index structures is an important problem, because disk I/O dominates the cost of queries. In this paper, we compare existing algorithms for uniform, nonuniform static and nonuniform dynamic accress patterns. We experimentally show that the LRU-2 method is better than the other methods. We also propose an efficient implementation of the LRU-2 algorithm. In the second art of the paper, we propose a new buffering algorithm for a distributed system where each machine has its own buffer. We shwo experimentally that this method performs better than other buffering techniques.