论文标题
带有多元分区的B-Trees的存储管理
Storage Management with Multi-Version Partitioned B-Trees
论文作者
论文摘要
数据库管理系统和K/V商店在可更新的数据集上运行 - 大大超过了可用的主内存的大小。基于树的K/V存储管理结构在存储引擎中特别受欢迎。 B+树允许持续的搜索性能，但是，写入的工作负载效率低下的写入模式对辅助存储设备和性能特征差。 LSM -树通过水平分区数据的水平分区来克服这个问题 - 足够小以完全驻留在主内存中，但需要频繁维护以维持搜索性能。 首先，我们建议在K/V商店（例如K/V商店）中，将多反之形分区的BTREE（MV-PBT）作为唯一存储和索引管理结构。其次，我们将MV-PBT与LSM-Trees进行比较。 MV-PBT中的逻辑水平分区允许利用现代B $^+$ - 在结构的小透明和内存居民部分中的最新进展。结构特性维持稳定的读取性能，得出有效的写入模式并减少写入放大。 我们将MV-PBT集成在Wiredtiger KV存储引擎中。与LSM-Trees相比，MV-PBT与YCSB工作负载中的B+树相比，与LSM-Trees相比，稳定吞吐量高达2倍。
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.
