Multiversion Concurrency Control for Multiversion B-Trees
2026-06-08 • Databases
DatabasesData Structures and Algorithms
AI summaryⓘ
The authors address how to manage multiple data versions efficiently in databases. Traditional methods use version chains that slow down reading and can cause conflicts during writing. They redesigned an existing complex structure called the multiversion B-tree into the concurrent MVBT (cMVBT), which allows fast, conflict-free scanning without locks and supports smooth background cleanup. Their tests show cMVBT performs better than current methods, especially in handling lots of mixed reading and writing. This approach aims to improve how databases handle concurrent access to historical data versions.
Multiversion concurrency controlB+ treeVersion chainsMultiversion B-tree (MVBT)Optimistic concurrency controlRange scansGarbage collectionWrite throughputDatabase concurrencyFree-space management
Authors
Amir Tonta, Bernhard Seeger, Eljas Soisalon-Soininen
Abstract
Multiversion concurrency control (MVCC) enables scans to read data from a committed snapshot (version), reducing conflicts with write operations compared to traditional concurrency approaches. Currently, versioned records are often managed in a B$^+$-tree using version chains. However, version chains introduce overhead during scans and can still lead to conflicts between scans and writers. The multiversion B-tree (MVBT) was designed for optimal range scan performance on arbitrary versions, but has been considered impractical due to its structural complexity and, until recently, the lack of effective concurrency control. In this paper, we present the concurrent MVBT (cMVBT), a redesign of the MVBT featuring a novel concurrency control protocol that uses optimistic latches for write operations and requires no latches for range scans, while preserving all the optimality guarantees of the original MVBT. Additionally, cMVBT supports continuous garbage collection without activity spikes, seamlessly integrating free-space management. Experiments with mixed workloads derived from a standard benchmark show that the cMVBT achieves low overhead, high write throughput, and excellent range scan performance, outperforming state-of-the-art methods based on version chains.