BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees

Summary: BP-tree breaks the B-tree point/range tradeoff by pairing small internal nodes with large leaves backed by a buffered partitioned array (BPA) that delays key ordering for cheap inserts. It preserves point throughput while delivering up to 30× faster large scans than Masstree. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: he0891d0f1d72a06d
Venue: VLDB
Year: 2023
Pagerank: 5.5522404e-05
Overall Rank: 7,325 | 50.76%
DOI: 10.14778/3611479.3611502

Incoming Non-self Citations Over Time

Authors

1. Helen Xu (Lawrence Berkeley National Laboratory)
2. Amanda Li (Massachusetts Institute of Technology)
3. Brian Wheatman (Johns Hopkins University)
4. Manoj Marneni (University of Utah)
5. Prashant Pandey (University of Utah)

BibTeX Citation

@article{xu_vldb23,
        title = {{BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees}},
        author = {Xu, Helen and Li, Amanda and Wheatman, Brian and Marneni, Manoj and Pandey, Prashant},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {11},
        pages = {2976--2989},
        doi = {10.14778/3611479.3611502},
        url = {https://doi.org/10.14778/3611479.3611502},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,484	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	5.7696173e-05
9,699	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.138658e-05
9,727	Tabular: Efficiently Building Efficient Indexes	2025	VLDB	5.1349531e-05
9,866	Zombie Hashing: Reanimating Tombstones in a Graveyard	2025	SIGMOD	5.1176637e-05
9,998	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.0979044e-05
10,428	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	4.9793485e-05
10,615	Aeris Filter: A Strongly and Monotonically Adaptive Range Filter	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
69	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037950385
106	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033526937
236	LinkBench: a Database Benchmark Based on the Facebook Social Graph	2013	SIGMOD	0.00023671522
548	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016569534
907	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00013158824
971	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012766019
1,241	BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications	2017	SIGMOD	0.00011378254
1,303	Realtime Data Processing at Facebook	2016	SIGMOD	0.0001110427
1,320	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	0.00011045319
1,605	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	0.00010093796
1,757	Write-Optimized B-Trees	2004	VLDB	9.7131504e-05
2,499	Towards Scalable Real-time Analytics: An Architecture for Scale-out of OLxP Workloads	2015	VLDB	8.3815142e-05
3,122	Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database	2015	SIGMOD	7.6236292e-05
3,847	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	6.9831533e-05
4,048	Fast Scans on Key-Value Stores	2017	VLDB	6.8304396e-05
9,683	S3: A Scalable In-memory Skip-List Index for Key-Value Store	2019	VLDB	5.1426496e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,970	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB
2	1,841	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
3	5,661	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
4	11,232	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
5	12,320	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
6	2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
7	11,237	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB
8	548	Improving Index Performance through Prefetching	2001	SIGMOD
9	9,998	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
10	6,484	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB