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

Summary: BP-tree uses asymmetric nodes (small internals, large leaves) and a buffered partitioned array (BPA) that postpones ordering to make inserts cheap while enabling large-leaf scans. Matches/exceeds Masstree/OpenBw-tree point throughput (0.94–1.2x) and yields ≈7–30x faster range scans. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13138
Venue: VLDB
Year: 2023
Pagerank: 4.6109825e-05
Overall Rank: 7,995 | 44.39%
DOI: 10.14778/3611479.3611502

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,154	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	4.815267e-05
9,404	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	4.3441378e-05
10,137	Aeris Filter: A Strongly and Monotonically Adaptive Range Filter	2026	SIGMOD	4.1945683e-05
10,368	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1945683e-05
10,527	Zombie Hashing: Reanimating Tombstones in a Graveyard	2025	SIGMOD	4.1945683e-05
10,583	Tabular: Efficiently Building Efficient Indexes	2025	VLDB	4.1945683e-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
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
145	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.0004138408
281	LinkBench: a Database Benchmark Based on the Facebook Social Graph	2013	SIGMOD	0.0002906793
531	Improving Index Performance through Prefetching	2001	SIGMOD	0.00020790058
1,087	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00014162909
1,312	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012652548
1,480	Write-Optimized B-Trees	2004	VLDB	0.00011746722
1,507	BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications	2017	SIGMOD	0.00011617967
1,613	Realtime Data Processing at Facebook	2016	SIGMOD	0.00011140777
2,157	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	9.416022e-05
2,394	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	8.9001843e-05
2,844	Towards Scalable Real-time Analytics: An Architecture for Scale-out of OLxP Workloads	2015	VLDB	8.0243849e-05
3,388	Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database	2015	SIGMOD	7.1571148e-05
4,236	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	6.3335374e-05
4,642	Fast Scans on Key-Value Stores	2017	VLDB	6.0267293e-05
9,373	S3: A Scalable In-memory Skip-List Index for Key-Value Store	2019	VLDB	4.3479874e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,809	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.00010483957
7,923	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	4.6155204e-05
5,239	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	5.6106291e-05
10,556	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	4.1945683e-05
11,822	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1945683e-05
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
10,562	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1945683e-05
531	Improving Index Performance through Prefetching	2001	SIGMOD	0.00020790058
10,368	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1945683e-05
7,154	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	4.815267e-05