Co-design of B+-tree Index with Emerging Zone Interfaces for Small-sized Key-value Pairs
Jinlei Hu, Bo Chen, Hong Jiang, M. X. Zhang, Jing Hu, Jianxi Chen, Dan Feng · ACM Transactions on Architecture and Code Optimization · 2025
The host-side and append-only zone interface offers new opportunities for existing key-value stores (KVSs), especially in reducing the flash-layer write amplification. While existing works focused on leveraging the zone interface for LSM-Tree-based KVSs, the potential advantages for B + -Tree-based KVSs remain under-explored. Through in-depth experimental observations, we identify three key opportunities for B + -Tree-based KVSs: superior read performance, flash-friendly append operations, and the ability to directly manage flash media. However, existing B + -Tree-based KVSs designed for block SSDs rely on inefficient file system layers to adapt to the idiosyncratic zone interface, and achieve reduced write amplification by seriously sacrificing read performance. We proposed a write-optimized B + -Tree-based key-value store ZKV, designed to minimize write amplification through the zone interface without sacrificing read performance. ZKV employs a three-level buffer structure to enable its core index structure Z + -Tree to be zone-interface efficient, including a tree-level merged filter, a leaf-level adaptive delta buffer, and an efficient zone-level management module ZFlusher. Through the three-level buffer structure, Z + -Tree effectively leverages the zone interface by converting small-size random write operations into flash-friendly large-block append operations. Our evaluations on a real ZNS SSD device demonstrate that ZKV achieves up to 3.12x/2.53x higher insert/read throughput than the current buffered-B + -Tree-based KVSs under YCSB workloads. Under three additional real-world workloads, ZKV matches the write performance of LSM-Tree-based RocksDB while delivering the read performance of B + -Tree-based WiredTiger.