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: h4582926db859f0d9
Venue: SIGMOD
Year: 2002
Pagerank: 0.00010146135
Overall Rank: 1,586 | 89.34%
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
282	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022264207
668	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.00014964806
939	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.00012970078
1,107	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00011993663
1,757	Write-Optimized B-Trees	2004	VLDB	9.7131504e-05
2,673	Asynchronous Memory Access Chaining	2016	VLDB	8.1482775e-05
3,709	CoroBase: Coroutine-Oriented Main-Memory Database Engine	2021	VLDB	7.0791362e-05
4,243	The Art of Latency Hiding in Modern Database Engines	2024	VLDB	6.7069789e-05
4,871	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	6.3737342e-05
5,737	Durable Write Cache in Flash Memory SSD for Relational and NoSQL Databases	2014	SIGMOD	6.0133439e-05
8,396	ADDICT: Advanced Instruction Chasing for Transactions	2014	VLDB	5.3403216e-05
8,532	AirIndex: Versatile Index Tuning Through Data and Storage	2023	SIGMOD	5.3217474e-05
9,456	How to Stop Under-Utilization and Love Multicores	2014	SIGMOD	5.1735054e-05
9,772	Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics	2003	VLDB	5.1324546e-05
10,727	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	4.9793485e-05
11,237	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.9793485e-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
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043805923
69	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037950385
110	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00032700879
207	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00024970987
229	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00023911856
548	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016569534
2,994	The Value of Merge-Join and Hash-Join in SQL Server	1999	VLDB	7.7710643e-05

Semantically Similar Papers

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