Buffering of Index Structures

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 access 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 part of the paper, we propose a new buffering algorithm for a distributed system where each machine has its own buffer. We show experimentally that this method performs better than other buffering techniques.