FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update

Summary: FB+-tree hybridizes B+-trees and tries by using multi-byte common-prefix “features” for cache-friendly branching while preserving balance and scan efficiency. A link/optimistic-lock protocol enables latch-free updates, delivering up to 3.7× higher throughput than popular B+-trees under contention. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14008
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,829 | 25.71%
DOI: 10.14778/3725688.3725691

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yuan Chen (Wuhan University)
2. Ao Li (Wuhan University)
3. Wenhai Li (Wuhan University)
4. Lingfeng Deng (Wuhan University)

BibTeX Citation

@article{chen_vldb25,
        title = {{FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update}},
        author = {Chen, Yuan and Li, Ao and Li, Wenhai and Deng, Lingfeng},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {6},
        pages = {1579--1592},
        doi = {10.14778/3725688.3725691},
        url = {https://doi.org/10.14778/3725688.3725691},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 28 of 28 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
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
278	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022476841
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
491	FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory	2016	SIGMOD	0.00017575163
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,112	Cache-Oblivious String B-trees	2006	PODS	0.00012125766
1,390	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	0.00010942775
1,567	Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance	2002	SIGMOD	0.00010343873
1,710	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB	9.9537123e-05
1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.6941032e-05
1,822	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.6765747e-05
1,823	LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory	2020	VLDB	9.6739945e-05
2,888	AI Meets Database: AI4DB and DB4AI	2021	SIGMOD	7.9941489e-05
2,910	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	7.9700885e-05
3,378	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	7.4587887e-05
5,261	Oasis: An Optimal Disjoint Segmented Learned Range Filter	2024	VLDB	6.2955539e-05
6,462	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	5.8717744e-05
6,687	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.8022308e-05
7,224	LITS: An Optimized Learned Index for Strings	2024	VLDB	5.6675134e-05
7,368	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB	5.6315363e-05
7,392	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	5.6265456e-05
8,474	OptiQL: Robust Optimistic Locking for Memory-Optimized Indexes	2023	SIGMOD	5.4172941e-05
10,009	Performance Guarantees for B-trees with Different-Sized Atomic Keys	2010	PODS	5.1785299e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	278	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD
2	10,824	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
3	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
4	5,993	NBTree: a Lock-free PM-friendly Persistent B+-Tree for eADR-enabled PM Systems	2022	VLDB
5	948	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB
6	7,189	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB
7	491	FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory	2016	SIGMOD
8	545	Improving Index Performance through Prefetching	2001	SIGMOD
9	6,742	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB
10	1,567	Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance	2002	SIGMOD