Index Access with a Finite Buffer

Summary: Analyzes buffer-fault rates for repeated clustered-index access in B-trees under finite memory. Shows conventional LRU is suboptimal; introduces ILRU (uniformly superior, especially with small buffers) and OLRU (optimal for uniform reference densities), with Zipfian behavior discussed. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h97366e8f2c5f654d
Venue: VLDB
Year: 1987
Pagerank: 5.8596628e-05
Overall Rank: 6,172 | 58.52%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Giovanni Maria Sacco (University of Turin)

BibTeX Citation

@article{sacco_vldb87,
        title = {{Index Access with a Finite Buffer}},
        author = {Sacco, Giovanni Maria},
        journal = {PVLDB},
        series = {{VLDB} '87},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,913	Clock2Q+: A Simple and Efficient Replacement Algorithm for Metadata Cache in VMware vSAN	2026	VLDB	4.9769913e-05
12,901	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.9769913e-05
13,207	GHOST: Fine Granularity Buffering of Index Pages	1999	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
128	An Evaluation of Buffer Management Strategies for Relational Database Systems	1985	VLDB	0.00030399615
607	A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model	1982	VLDB	0.00015595949

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,529	On the Analysis of Indexing Schemes	1997	PODS
2	8,865	Adaptive Index Structures	2002	VLDB
3	9,110	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
4	4,355	Interaction of Query Evaluation and Buffer Management for Information Retrieval	1998	SIGMOD
5	9,514	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
6	212	The LRU-K Page Replacement Algorithm For Database Disk Buffering	1993	SIGMOD
7	1,105	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB
8	13,207	GHOST: Fine Granularity Buffering of Index Pages	1999	VLDB
9	13,326	Estimating Page Fetches for Index Scans with Finite LRU Buffers	1994	SIGMOD
10	2,560	Extensible Buffer Management of Indexes	1992	VLDB