Enabling sequential-write-constrained B⁺-tree index scheme to upgrade shingled magnetic recording storage performance

When a shingle magnetic recording (SMR) drive has been widely applied to modern computer systems (e.g., archive file systems, big data computing systems, and large-scale database systems), storage system developers should thoroughly review whether current designs (e.g., index schemes and data placements) are appropriate for an SMR drive because of its sequential write constraint. Through many prior works excellently manage data in an SMR drive by integrating their proposed solutions into the driver layer, an index scheme over an SMR drive has never been optimized by any previous works because managing index over the SMR drive needs to jointly consider the properties of B⁺-tree and SMR natures (e.g., sequential write constraint and zone partitions) in a host storage system. Moreover, poor index management will result in terrible storage performance because an index manager is extensively used in file systems and database applications. For optimizing the B⁺-tree index structure over an SMR storage, this work identifies performance overheads caused by the B⁺-tree index structure in an SMR drive. By such observation, this study proposes a sequential-write-constrained B⁺-tree index scheme, namely SW-B⁺tree, which consists of an address redirection data structure, an SMR-aware node allocation mechanism, and a frequency-aware garbage collection strategy. According to our experiments, the SW-B⁺tree can improve the SMR storage performance 55% on average.