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.