Papers › FB^+-tree: A Memory-Optimized B^+-tree with Latch-Free Update
FB^+-tree: A Memory-Optimized B^+-tree with Latch-Free Update
Yuan Chen, Ao Li, Wenhai Li, Lingfeng Deng
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
B^+-trees are prevalent in traditional database systems due to their versatility and balanced structure. While binary search is typically utilized for branch operations, it may lead to inefficient cache utilization in main-memory scenarios. In contrast, trie-based index structures drive branch operations through prefix matching. While these structures generally produce fewer cache misses and are thus increasingly popular, they may underperform in range scans because of frequent pointer chasing. This paper proposes a new high-performance B^+-tree variant called \textbf{Feature B^+-tree (FB^+-tree)}. Similar to employing bit or byte for branch operation in tries, FB^+-tree progressively considers several bytes following the common prefix on each level of its inner nodes\textemdash referred to as features, which allows FB^+-tree to benefit from prefix skewness. FB^+-tree blurs the lines between B^+-trees and tries, while still retaining balance. In the best case, FB^+-tree almost becomes a trie, whereas in the worst case, it continues to function as a B^+-tree. Meanwhile, a crafted synchronization protocol that combines the link technique and optimistic lock is designed to support efficient concurrent index access. Distinctively, FB^+-tree leverages subtle atomic operations seamlessly coordinated with optimistic lock to facilitate latch-free updates, which can be easily extended to other structures. Intensive experiments on multiple workload-dataset combinations demonstrate that FB^+-tree shows comparable lookup performance to state-of-the-art trie-based indexes and outperforms popular B^+-trees by 2.3x∼3.7x under 96 threads. FB^+-tree also exhibits significant potential on other workloads, especially update workloads under contention and scan workloads.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections