Index Access with a Finite Buffer

A buffer is a main-memory area used to reduce accessto disks. The buffer holds pages from secondary storage files. A processrequesting a page causesa fault if the pageis not in the buffer: the requestedpage is read into the buffer. If no buffer space is available, a page in the buffer is replaced by the requestedone. The solution of many relational queries (e.g.joins) require the repeatedaccessof 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 replacementsuategy, 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...