Index Access with a Finite Buffer
Giovanni Maria Sacco · Very Large Data Bases · 1987
A buffer is a main-memory area used to reduce access to disks. The buffer holds pages from secondary storage files. A process requesting a page causes a fault if the page is not in the buffer: the requested page is read into the buffer. If no buffer space is available, a page in the buffer is replaced by the requested one. The solution of many relational queries (e.g. joins) require the repeated access of a relation through a unique clustered index. The fault rate of such queries as a function of the available buffer size is analyzed. A B-tree structure is assumed, but the results presented here carry over to most other hierarchical index structures. It is shown that the LRU replacement suategy, commonly used with this type of access, is not the best strategy. Two alternative strategies, ILRU and OLRU, are proposed. ILRU is shown to be always better than LRU, especially for small buffer sizes and independently of the probability of page references. OLRU is proved to be optimal under the assumption of a uniform distribution of page reference densities. The behaviour of LRU and OLRU under distributions that violate this assumption (such as Zipfian distributions) is discussed.