DBScholar

Back to papers

Making B+-Trees Cache Conscious in Main Memory

Summary: Introduces a cache-conscious B+-Tree for in-memory workloads, addressing poor cache-line utilization of traditional B+-Trees. Retains incremental update efficiency while delivering cache-friendly lookups, positioning B+-Trees as a dynamic alternative to CSS-Trees for main memory indexing. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h5ffe6002427668c5
Venue
SIGMOD
Year
2000
Pagerank
0.00037950385
Overall Rank
69 | 99.54%
DOI
10.1145/342009.335449

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{rao_sigmod00,
        title = {{Making B+-Trees Cache Conscious in Main Memory}},
        author = {Rao, Jun and Ross, Kenneth A.},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335449},
        url = {https://dl.acm.org/doi/10.1145/342009.335449},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 76 citing papers.

Rank Citing Paper Year Venue Pagerank
14 MonetDB/X100: Hyper-Pipelining Query Execution 2005 CIDR 0.00064031282
40 The Case for Learned Index Structures 2018 SIGMOD 0.00046284649
70 The End of an Architectural Era (It’s Time for a Complete Rewrite) 2007 VLDB 0.00037859131
157 OLTP Through the Looking Glass, and What We Found There 2008 SIGMOD 0.00028317906
166 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00027254612
282 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00022264207
287 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00021970198
430 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018409112
502 FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory 2016 SIGMOD 0.00017250534
548 Improving Index Performance through Prefetching 2001 SIGMOD 0.00016569534
631 Persistent B+-Trees in Non-Volatile Main Memory 2015 VLDB 0.0001541723
668 Rethinking Database Algorithms for Phase Change Memory 2011 CIDR 0.00014964806
702 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00014673738
761 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.00014143602
907 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.00013158824
910 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013123912
939 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00012970078
1,041 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00012356709
1,107 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00011993663
1,335 Fast Updates on Read-Optimized Databases Using Multi-Core CPUs 2012 VLDB 0.0001099401
1,440 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010641888
1,586 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010146135
1,605 The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models 2018 SIGMOD 0.00010093796
1,717 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.8016891e-05
1,841 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 9.5268075e-05
1,854 LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory 2020 VLDB 9.4991601e-05
1,855 PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors 2011 VLDB 9.4973014e-05
2,016 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1771614e-05
2,238 Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations 2019 SIGMOD 8.7751619e-05
2,277 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 8.7075835e-05
2,383 The Uncracked Pieces in Database Cracking 2014 VLDB 8.5435328e-05
2,673 Asynchronous Memory Access Chaining 2016 VLDB 8.1482775e-05
2,699 Database Servers on Chip Multiprocessors: Limitations and Opportunities 2007 CIDR 8.1195744e-05
2,809 Exploiting Coroutines to Attack the "Killer Nanoseconds" 2018 VLDB 7.9825078e-05
2,866 APEX: A High-Performance Learned Index on Persistent Memory 2022 VLDB 7.9258875e-05
2,925 Interleaving with Coroutines: A Practical Approach for Robust Index Joins 2018 VLDB 7.8482706e-05
3,375 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.3608441e-05
3,599 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 7.1773938e-05
3,674 P*TIME: Highly Scalable OLTP DBMS for Managing Update-Intensive Stream Workload 2004 VLDB 7.1076866e-05
3,709 CoroBase: Coroutine-Oriented Main-Memory Database Engine 2021 VLDB 7.0791362e-05
3,803 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.0127652e-05
4,027 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.8456902e-05
4,070 SharkDB: An In-Memory Storage System for Massive Trajectory Data 2015 SIGMOD 6.8213576e-05
4,680 Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes 2018 VLDB 6.4722037e-05
4,721 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 6.4541703e-05
4,871 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 6.3737342e-05
4,885 Design Tradeoffs of Data Access Methods 2016 SIGMOD 6.3706825e-05
5,032 Put an Elephant into a Fridge: Optimizing Cache Efficiency for In-memory Key-value Stores 2020 VLDB 6.3053972e-05
5,274 Only Aggressive Elephants are Fast Elephants 2012 VLDB 6.2005706e-05
5,397 Order-Preserving Key Compression for In-Memory Search Trees 2020 SIGMOD 6.1490013e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
27 Database Architecture Optimized for the New Bottleneck: Memory Access 1999 VLDB 0.0005158963
76 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00036898845
110 DBMSs On A Modern Processor: Where Does Time Go? 1999 VLDB 0.00032700879
207 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00024970987
229 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00023911856
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 14,803 Towards an Optimal Data-Structure: CB-trees 1984 VLDB
2 11,237 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB
3 1,586 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD
4 548 Improving Index Performance through Prefetching 2001 SIGMOD
5 1,717 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB
6 1,841 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD
7 2,016 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD
8 1,074 Cache-Oblivious String B-trees 2006 PODS
9 1,107 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB
10 207 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB