Optimizing Structural Modification Operation for B+-Tree on Byte-Addressable Devices
Dingze Hong, Jinlei Hu, Jianxi Chen, Dan Feng, Jian Liu · 2024
Persistent Memory (PM) offers both byte-address ability and non-volatility, making it well-suited for accelerating$\mathrm{B}^{+}$-Tree indexes. However, existing persistent$\mathrm{B}^{+}$-Tree indexes face significant performance challenges due to high structural modification operation (SMO) overhead. SMOs often result in costly item migrations and increased tail latency, which severely degrade the overall performance. In this paper, we present SSTree, a high-performance$\mathrm{B}^{+}$– Tree index specifically optimized to address SMO overhead. SSTree introduces three key innovations: (i) efficient leaf node expansion using a list of subnodes to postpone expensive node splits, (ii) delegated fingerprints to speed up search operations across subnodes, and (iii) proactive subnode compaction that employs out-of-place updates to optimize item organization. Our evaluation demonstrates that SSTree delivers up to$4.38\times$higher write throughput and up to$62\times$lower tail latency compared to state-of-the-art persistent$\mathrm{B}^{+}$-Tree indexes.