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
3334
Venue
SIGMOD
Year
2001
Pagerank
0.00016766463
Overall Rank
545 | 96.27%
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.0006312782
278 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00022476841
293 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00022259273
447 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018322593
621 Persistent B+-Trees in Non-Volatile Main Memory 2015 VLDB 0.00015695264
658 Rethinking Database Algorithms for Phase Change Memory 2011 CIDR 0.0001523554
882 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.0001342403
932 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00013119305
1,110 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00012140661
1,347 X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing 2019 SIGMOD 0.00011073571
1,511 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010538011
1,551 Updatable Learned Index with Precise Positions 2021 VLDB 0.00010381398
1,567 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010343873
1,629 Positional Update Handling in Column Stores 2010 SIGMOD 0.00010184131
1,823 LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory 2020 VLDB 9.6739945e-05
2,394 A Case for Staged Database Systems 2003 CIDR 8.6362653e-05
2,649 Asynchronous Memory Access Chaining 2016 VLDB 8.2926258e-05
3,378 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.4587887e-05
3,644 CoroBase: Coroutine-Oriented Main-Memory Database Engine 2021 VLDB 7.2306862e-05
3,729 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.1683974e-05
3,969 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.9837297e-05
4,440 The Art of Latency Hiding in Modern Database Engines 2024 VLDB 6.7049797e-05
4,772 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 6.5154736e-05
6,003 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB 6.0130964e-05
6,682 STEPS Towards Cache-Resident Transaction Processing 2004 VLDB 5.8039833e-05
7,189 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 5.6775326e-05
8,765 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.3766157e-05
9,106 AirIndex: Versatile Index Tuning Through Data and Storage 2023 SIGMOD 5.3226167e-05
9,498 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 5.2606222e-05
10,682 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 5.093636e-05
10,829 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 5.093636e-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
67 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00038461275
74 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00037330605
109 DBMSs On A Modern Processor: Where Does Time Go? 1999 VLDB 0.000331207
204 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00025342994
215 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00024507963
219 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00024293529
1,355 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.0001105702
Previous Page 1 / 1 Next

Semantically Similar Papers

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