DBScholar

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
h1f096b579277a428
Venue
SIGMOD
Year
2001
Pagerank
0.00016534019
Overall Rank
548 | 96.33%
DOI
10.1145/375663.375688

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{chen_sigmod01,
        title = {{Improving Index Performance through Prefetching}},
        author = {Chen, Shimin and Gibbons, Phillip B. and Mowry, Todd C.},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375688},
        url = {https://dl.acm.org/doi/10.1145/375663.375688},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
14 MonetDB/X100: Hyper-Pipelining Query Execution 2005 CIDR 0.00063972112
280 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00022267903
289 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00021955394
427 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018429918
632 Persistent B+-Trees in Non-Volatile Main Memory 2015 VLDB 0.00015366735
671 Rethinking Database Algorithms for Phase Change Memory 2011 CIDR 0.00014912266
906 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.00013129817
943 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.0001293608
1,106 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00011960288
1,324 X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing 2019 SIGMOD 0.00011019001
1,440 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010630613
1,529 Updatable Learned Index with Precise Positions 2021 VLDB 0.00010320909
1,588 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010115044
1,637 Positional Update Handling in Column Stores 2010 SIGMOD 9.9898497e-05
1,863 LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory 2020 VLDB 9.4679185e-05
2,447 A Case for Staged Database Systems 2003 CIDR 8.4378829e-05
2,681 Asynchronous Memory Access Chaining 2016 VLDB 8.1203826e-05
3,383 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.3393628e-05
3,716 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.0541948e-05
3,719 CoroBase: Coroutine-Oriented Main-Memory Database Engine 2021 VLDB 7.0525094e-05
4,042 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.8217193e-05
4,071 The Art of Latency Hiding in Modern Database Engines 2024 VLDB 6.8073218e-05
4,893 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 6.3500196e-05
6,108 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB 5.8677102e-05
6,804 STEPS Towards Cache-Resident Transaction Processing 2004 VLDB 5.66191e-05
7,049 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 5.5967284e-05
8,558 AirIndex: Versatile Index Tuning Through Data and Storage 2023 SIGMOD 5.3016395e-05
8,955 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.2361195e-05
9,709 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 5.1251439e-05
11,191 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.9605343e-05
11,301 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.9605343e-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
68 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00037861537
77 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00036821827
111 DBMSs On A Modern Processor: Where Does Time Go? 1999 VLDB 0.00032621499
209 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00024915373
223 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00024059196
230 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00023845485
1,386 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.00010809129
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,076 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB
2 6,500 Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index 2024 VLDB
3 68 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD
4 6,597 Efficient Search of Multidimensional B-Trees 1995 VLDB
5 3,802 B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives 2012 VLDB
6 11,301 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB
7 7,049 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB
8 1,106 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB
9 1,849 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD
10 1,588 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD