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.00037861537
Overall Rank: 68 | 99.55%
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,839	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	5.957817e-05
5,914	HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication	2020	VLDB	5.9324967e-05
6,139	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	5.8567401e-05
6,332	Robust Performance of Main Memory Data Structures by Configuration	2020	SIGMOD	5.7934902e-05
6,433	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.7684496e-05
7,049	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.5967284e-05
7,516	B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	5.4896042e-05
7,727	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB	5.4518367e-05
8,195	Hyperion: Building the Largest In-memory Search Tree	2019	SIGMOD	5.3639085e-05
8,247	The HV-tree: a Memory Hierarchy Aware Version Index	2010	VLDB	5.3548467e-05
8,266	Index Checkpoints for Instant Recovery in In-Memory Database Systems	2022	VLDB	5.3498895e-05
8,638	Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines	2024	SIGMOD	5.2825944e-05
8,806	QPPT: Query Processing on Prefix Trees	2013	CIDR	5.257679e-05
8,955	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	5.2361195e-05
9,208	ERIS Live: A NUMA-Aware In-Memory Storage Engine for Tera-Scale Multiprocessor Systems	2014	SIGMOD	5.1941894e-05
9,361	Databases in the Era of Memory-Centric Computing	2025	CIDR	5.174177e-05
9,585	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.1406489e-05
9,640	MCC-DB: Minimizing Cache Conflicts in Multi-core Processors for Databases	2009	VLDB	5.134315e-05
9,709	S3: A Scalable In-memory Skip-List Index for Key-Value Store	2019	VLDB	5.1251439e-05
9,786	Data Structure Engineering For Byte-Addressable Non-Volatile Memory	2017	SIGMOD	5.115551e-05
9,832	Declarative Memory Services	2026	CIDR	5.1064323e-05
10,299	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.0302708e-05
10,506	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	4.9605343e-05
10,798	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	4.9605343e-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

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.0005146739
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
230	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00023845485

Semantically Similar Papers

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