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: 3270
Venue: SIGMOD
Year: 2000
Pagerank: 0.00038461275
Overall Rank: 67 | 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,715	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	6.1105343e-05
5,823	HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication	2020	VLDB	6.0752299e-05
6,012	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	6.0102675e-05
6,187	Robust Performance of Main Memory Data Structures by Configuration	2020	SIGMOD	5.9485755e-05
6,329	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.9109943e-05
7,189	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.6775326e-05
7,768	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB	5.5475685e-05
8,015	Hyperion: Building the Largest In-memory Search Tree	2019	SIGMOD	5.5071737e-05
8,099	Index Checkpoints for Instant Recovery in In-Memory Database Systems	2022	VLDB	5.4873906e-05
8,207	The HV-tree: a Memory Hierarchy Aware Version Index	2010	VLDB	5.4666057e-05
8,255	B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	5.4574671e-05
8,463	Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines	2024	SIGMOD	5.4205593e-05
8,625	QPPT: Query Processing on Prefix Trees	2013	CIDR	5.3979222e-05
8,765	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	5.3766157e-05
9,011	ERIS Live: A NUMA-Aware In-Memory Storage Engine for Tera-Scale Multiprocessor Systems	2014	SIGMOD	5.3324807e-05
9,449	MCC-DB: Minimizing Cache Conflicts in Multi-core Processors for Databases	2009	VLDB	5.2665098e-05
9,498	S3: A Scalable In-memory Skip-List Index for Key-Value Store	2019	VLDB	5.2606222e-05
9,573	Data Structure Engineering For Byte-Addressable Non-Volatile Memory	2017	SIGMOD	5.2528121e-05
9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.214913e-05
9,890	Databases in the Era of Memory-Centric Computing	2025	CIDR	5.1997534e-05
10,067	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.1643809e-05
10,127	Declarative Memory Services	2026	CIDR	5.093636e-05
10,212	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	5.093636e-05
10,545	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	5.093636e-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

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
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
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
219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00024293529

Semantically Similar Papers

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