TY  - CHAP
U1  - Konferenzveröffentlichung
A1  - Riegger, Christian
A1  - Petrov, Ilia
ED  - Chiusano, Silvia
ED  - Cerquitelli, Tania
ED  - Wrembel, Robert
T1  - Storage management with multi-version partitioned BTrees
T2  - Advances in databases and information systems : 26th European Conference, ADBIS 2022, Turin, Italy, September 5-8, 2022, proceedings. - (Lecture notes in computer science ; 13389)
N2  - Database management systems and K/V-Stores operate on updatable datasets – massively exceeding the size of available main memory. Tree-based K/V storage management structures became particularly popular in storage engines. B+ -Trees [1, 4] allow constant search performance, however write-heavy workloads yield in inefficient write patterns to secondary storage devices and poor performance characteristics. LSM-Trees [16, 23] overcome this issue by horizontal partitioning fractions of data – small enough to fully reside in main memory, but require frequent maintenance to sustain search performance.

Firstly, we propose Multi-Version Partitioned BTrees (MV-PBT) as sole storage and index management structure in key-sorted storage engines like K/V-Stores. Secondly, we compare MV-PBT against LSM-Trees. The logical horizontal partitioning in MV-PBT allows leveraging recent advances in modern B+ -Tree techniques in a small transparent and memory resident portion of the structure. Structural properties sustain steady read performance, yielding efficient write patterns and reducing write amplification.

We integrated MV-PBT in the WiredTiger [15] KV storage engine. MV-PBT offers an up to 2× increased steady throughput in comparison to LSM-Trees and several orders of magnitude in comparison to B+ -Trees in a YCSB [5] workload.
KW  - storage engine
KW  - storage management
KW  - append storage
Y1  - 2022
SN  - 978-3-031-15740-0
SB  - 978-3-031-15740-0
U6  - https://doi.org/10.1007/978-3-031-15740-0_19
DO  - https://doi.org/10.1007/978-3-031-15740-0_19
SP  - 255
EP  - 269
S1  - 15
PB  - Springer
CY  - Cham
ER  -