Design of a Write-Optimized Data Store
The WriteBuffer (WB) tree is a new write-optimized data structure that can be used to implement per-node storage in unordered key-value stores. The WB tree provides faster writes than the Log-Structured Merge (LSM) tree that is used in many current high-performance key-value stores. It achieves this by replacing compactions in LSM trees, which are I/O-intensive, with light-weight spills and splits, along with other techniques. By providing nearly 30 higher write performance compared to current high-performance key-value stores, while providing comparable read performance (1-2 I/Os per read using 1-2B per key of memory), the WB tree addresses the needs of a class of increasingly popular write-intensive workloads.