Database Paper Browser

Back to papers

Improving Index Performance through Prefetching

Summary: pB+-Trees widen nodes by prefetching, lowering height and speeding searches/updates 1.2–1.5×, outperforming Cache-Sensitive B+-Trees. For range scans, leaf-pointer arrays enable far-ahead prefetching, delivering >6× speedups on 1000+ keys and hiding disk latency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3272
Venue
SIGMOD
Year
2001
Pagerank
0.00020790058
Overall Rank
531 | 96.31%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
35 MonetDB/X100: Hyper-Pipelining Query Execution 2005 CIDR 0.00076197749
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026768139
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
819 Persistent B+-Trees in Non-Volatile Main Memory 2015 VLDB 0.00016298164
826 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00016224841
1,050 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00014453896
1,087 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.00014162909
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013406526
1,659 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010980701
1,676 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010946423
1,949 Positional Update Handling in Column Stores 2010 SIGMOD 9.9864085e-05
2,004 X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing 2019 SIGMOD 9.811707e-05
2,328 A Case for Staged Database Systems 2003 CIDR 9.0225171e-05
2,510 LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory 2020 VLDB 8.6204284e-05
2,552 Updatable Learned Index with Precise Positions 2021 VLDB 8.5530411e-05
3,175 Asynchronous Memory Access Chaining 2016 VLDB 7.438501e-05
3,623 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.9062146e-05
3,777 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 6.7750901e-05
4,184 CoroBase: Coroutine-Oriented Main-Memory Database Engine 2021 VLDB 6.3779731e-05
4,646 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 6.0250374e-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
6,058 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB 5.2310254e-05
6,447 STEPS Towards Cache-Resident Transaction Processing 2004 VLDB 5.0588602e-05
7,995 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6109825e-05
8,562 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4937074e-05
9,095 AirIndex: Versatile Index Tuning Through Data and Storage 2023 SIGMOD 4.3975034e-05
9,373 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 4.3479874e-05
10,396 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.1945683e-05
10,562 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
81 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00055548574
84 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00053866006
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
1,309 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.00012660929
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,774 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010604097
7,154 Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index 2024 VLDB 4.815267e-05
103 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049150032
6,480 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0475112e-05
4,130 B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives 2012 VLDB 6.4256779e-05
10,562 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1945683e-05
7,995 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6109825e-05
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013406526
1,809 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 0.00010483957
1,659 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010980701