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: 13326
Venue: VLDB
Year: 2023
Pagerank: 5.6775326e-05
Overall Rank: 7,189 | 50.68%
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,742	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	5.7862414e-05
9,518	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.256602e-05
9,547	Tabular: Efficiently Building Efficient Indexes	2025	VLDB	5.2528121e-05
9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.214913e-05
10,212	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	5.093636e-05
10,426	Aeris Filter: A Strongly and Monotonically Adaptive Range Filter	2026	SIGMOD	5.093636e-05
10,799	Zombie Hashing: Reanimating Tombstones in a Graveyard	2025	SIGMOD	5.093636e-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
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
105	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033877899
232	LinkBench: a Database Benchmark Based on the Facebook Social Graph	2013	SIGMOD	0.00023830978
545	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016766463
882	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.0001342403
964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012934147
1,238	BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications	2017	SIGMOD	0.00011543368
1,389	Realtime Data Processing at Facebook	2016	SIGMOD	0.00010943767
1,390	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	0.00010942775
1,616	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	0.00010213691
1,731	Write-Optimized B-Trees	2004	VLDB	9.9081882e-05
2,583	Towards Scalable Real-time Analytics: An Architecture for Scale-out of OLxP Workloads	2015	VLDB	8.3849987e-05
3,082	Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database	2015	SIGMOD	7.7725834e-05
3,778	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	7.1334329e-05
4,058	Fast Scans on Key-Value Stores	2017	VLDB	6.9335663e-05
9,498	S3: A Scalable In-memory Skip-List Index for Key-Value Store	2019	VLDB	5.2606222e-05

Semantically Similar Papers

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