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
3273
Venue
SIGMOD
Year
2001
Pagerank
0.00018976783
Overall Rank
622 | 95.68%
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.00076209479
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026756534
382 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00024888997
687 Rethinking Database Algorithms for Phase Change Memory 2011 CIDR 0.00018097447
809 Persistent B+-Trees in Non-Volatile Main Memory 2015 VLDB 0.00016409797
819 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00016237497
1,046 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00014446882
1,085 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.00014173956
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013404419
1,659 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010970279
1,670 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010944596
1,932 X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing 2019 SIGMOD 0.00010050776
1,949 Positional Update Handling in Column Stores 2010 SIGMOD 9.9934641e-05
2,329 A Case for Staged Database Systems 2003 CIDR 9.0237899e-05
2,508 LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory 2020 VLDB 8.6251065e-05
2,550 Updatable Learned Index with Precise Positions 2021 VLDB 8.5569576e-05
3,179 Asynchronous Memory Access Chaining 2016 VLDB 7.4350144e-05
3,627 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.900129e-05
3,760 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 6.7790524e-05
4,184 CoroBase: Coroutine-Oriented Main-Memory Database Engine 2021 VLDB 6.3718449e-05
4,830 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 5.8884997e-05
5,060 The Art of Latency Hiding in Modern Database Engines 2024 VLDB 5.7175345e-05
5,226 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 5.6164816e-05
6,063 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB 5.2259989e-05
6,439 STEPS Towards Cache-Resident Transaction Processing 2004 VLDB 5.0550138e-05
7,990 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6086117e-05
8,559 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4893996e-05
9,093 AirIndex: Versatile Index Tuning Through Data and Storage 2023 SIGMOD 4.3932886e-05
9,383 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 4.343888e-05
10,407 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.1905499e-05
10,571 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1905499e-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.00055253195
85 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00053652634
104 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049475932
124 DBMSs On A Modern Processor: Where Does Time Go? 1999 VLDB 0.0004501099
235 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00031980259
240 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00031526134
1,337 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.00012515176
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,766 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010611043
7,152 Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index 2024 VLDB 4.8126591e-05
104 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049475932
6,473 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0427056e-05
4,131 B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives 2012 VLDB 6.4203081e-05
10,571 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1905499e-05
7,990 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6086117e-05
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013404419
1,807 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 0.0001047644
1,659 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010970279