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: 3346
Venue: SIGMOD
Year: 2002
Pagerank: 0.00010980701
Overall Rank: 1,659 | 88.47%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
381	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00024873637
576	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.00019865648
1,050	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.00014453896
1,195	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00013406526
1,480	Write-Optimized B-Trees	2004	VLDB	0.00011746722
3,175	Asynchronous Memory Access Chaining	2016	VLDB	7.438501e-05
4,184	CoroBase: Coroutine-Oriented Main-Memory Database Engine	2021	VLDB	6.3779731e-05
5,219	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	5.6217069e-05
5,312	The Art of Latency Hiding in Modern Database Engines	2024	VLDB	5.5734224e-05
5,648	Durable Write Cache in Flash Memory SSD for Relational and NoSQL Databases	2014	SIGMOD	5.3915951e-05
8,265	ADDICT: Advanced Instruction Chasing for Transactions	2014	VLDB	4.5461133e-05
9,070	How to Stop Under-Utilization and Love Multicores	2014	SIGMOD	4.4031183e-05
9,095	AirIndex: Versatile Index Tuning Through Data and Storage	2023	SIGMOD	4.3975034e-05
9,442	Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics	2003	VLDB	4.3410889e-05
10,257	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	4.1945683e-05
10,562	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1945683e-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
80	Weaving Relations for Cache Performance	2001	VLDB	0.00055721729
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
124	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00045103515
233	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00032021526
238	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031642425
531	Improving Index Performance through Prefetching	2001	SIGMOD	0.00020790058
2,518	The Value of Merge-Join and Hash-Join in SQL Server	1999	VLDB	8.6089125e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,481	Buffered Persistence in B+ Trees	2024	SIGMOD	4.7180617e-05
14,292	Towards an Optimal Data-Structure: CB-trees	1984	VLDB	-
7,995	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	4.6109825e-05
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
10,368	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1945683e-05
5,098	Multi-Disk B-trees	1991	SIGMOD	5.7007294e-05
1,809	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.00010483957
7,154	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	4.815267e-05
10,562	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1945683e-05
531	Improving Index Performance through Prefetching	2001	SIGMOD	0.00020790058