  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
allow constant search performance, however write-heavy workloads yield in
inefficient write patterns to secondary storage devices and poor performance
characteristics. LSM-Trees 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 KV storage engine. MV-PBT offers an up
to 2x increased steady throughput in comparison to LSM-Trees and several orders
of magnitude in comparison to B+ Trees in a YCSB workload.
