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

Yu Pei Liang, Tseng Yi Chen, Yuan Hao Chang, Shuo Han Chen, Kam Yiu Lam, Wei Hsin Li, Wei Kuan Shih

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish
Article numbera66
JournalACM Transactions on Embedded Computing Systems
Issue number5s
StatePublished - Oct 2019


  • B-tree
  • File index
  • Sequential write
  • Shingled magnetic recording


Dive into the research topics of 'Enabling sequential-write-constrained B+-tree index scheme to upgrade shingled magnetic recording storage performance'. Together they form a unique fingerprint.

Cite this