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

1. Jun Rao (Columbia University)
2. Kenneth A. Ross (Columbia University)

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 26 of 76 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,827	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	5.979772e-05
5,906	HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication	2020	VLDB	5.9508926e-05
6,123	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	5.8789534e-05
6,317	Robust Performance of Main Memory Data Structures by Configuration	2020	SIGMOD	5.8154421e-05
6,434	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.7861149e-05
7,325	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.5522404e-05
7,710	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB	5.4713723e-05
7,816	B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	5.4481832e-05
8,174	Hyperion: Building the Largest In-memory Search Tree	2019	SIGMOD	5.3839613e-05
8,222	The HV-tree: a Memory Hierarchy Aware Version Index	2010	VLDB	5.3751545e-05
8,243	Index Checkpoints for Instant Recovery in In-Memory Database Systems	2022	VLDB	5.3701805e-05
8,620	Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines	2024	SIGMOD	5.301557e-05
8,780	QPPT: Query Processing on Prefix Trees	2013	CIDR	5.2776055e-05
8,927	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	5.2559789e-05
9,175	ERIS Live: A NUMA-Aware In-Memory Storage Engine for Tera-Scale Multiprocessor Systems	2014	SIGMOD	5.2135249e-05
9,617	MCC-DB: Minimizing Cache Conflicts in Multi-core Processors for Databases	2009	VLDB	5.1507816e-05
9,683	S3: A Scalable In-memory Skip-List Index for Key-Value Store	2019	VLDB	5.1426496e-05
9,749	Data Structure Engineering For Byte-Addressable Non-Volatile Memory	2017	SIGMOD	5.1349531e-05
9,793	Declarative Memory Services	2026	CIDR	5.1257999e-05
9,998	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.0979044e-05
10,074	Databases in the Era of Memory-Centric Computing	2025	CIDR	5.0855548e-05
10,266	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.0493495e-05
10,428	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	4.9793485e-05
10,727	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	4.9793485e-05
11,122	VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity	2025	SIGMOD	4.9793485e-05
11,237	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.9793485e-05

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

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