Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance

Summary: fpB+-Trees nest cache-optimized subtrees inside disk-optimized B+-Trees to balance cache and I/O. Disk-first and cache-first variants deliver cache gains (1.1–1.8x search, 4.2x scans, 20x updates) with minimal I/O impact; jump-pointer arrays prefetch leaves to speed range scans (2.5–5x on DB2). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3408
Venue: SIGMOD
Year: 2002
Pagerank: 0.00010343873
Overall Rank: 1,567 | 89.26%
DOI: 10.1145/564691.564710

Incoming Non-self Citations Over Time

Authors

1. Shimin Chen (Carnegie Mellon University)
2. Phillip B. Gibbons (AT&T; Intel)
3. Todd C. Mowry (Carnegie Mellon University)
4. Gary Valentin (IBM)

BibTeX Citation

@inproceedings{chen_sigmod02,
        title = {{Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance}},
        author = {Chen, Shimin and Gibbons, Phillip B. and Mowry, Todd C. and Valentin, Gary},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564710},
        url = {https://dl.acm.org/doi/10.1145/564691.564710},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
278	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022476841
658	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.0001523554
932	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.00013119305
1,110	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00012140661
1,731	Write-Optimized B-Trees	2004	VLDB	9.9081882e-05
2,649	Asynchronous Memory Access Chaining	2016	VLDB	8.2926258e-05
3,644	CoroBase: Coroutine-Oriented Main-Memory Database Engine	2021	VLDB	7.2306862e-05
4,440	The Art of Latency Hiding in Modern Database Engines	2024	VLDB	6.7049797e-05
4,772	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	6.5154736e-05
5,625	Durable Write Cache in Flash Memory SSD for Relational and NoSQL Databases	2014	SIGMOD	6.1448053e-05
8,315	ADDICT: Advanced Instruction Chasing for Transactions	2014	VLDB	5.4553606e-05
9,106	AirIndex: Versatile Index Tuning Through Data and Storage	2023	SIGMOD	5.3226167e-05
9,288	How to Stop Under-Utilization and Love Multicores	2014	SIGMOD	5.2912652e-05
9,609	Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics	2003	VLDB	5.2468818e-05
10,545	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	5.093636e-05
10,829	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
49	Weaving Relations for Cache Performance	2001	VLDB	0.00043781096
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
109	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.000331207
204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00025342994
219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00024293529
545	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016766463
2,952	The Value of Merge-Join and Hash-Join in SQL Server	1999	VLDB	7.9255489e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,906	Buffered Persistence in B+ Trees	2024	SIGMOD
2	14,493	Towards an Optimal Data-Structure: CB-trees	1984	VLDB
3	7,189	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB
4	67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD
5	9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
6	5,120	Multi-Disk B-trees	1991	SIGMOD
7	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
8	6,742	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB
9	10,829	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB
10	545	Improving Index Performance through Prefetching	2001	SIGMOD