A Case for Space Compaction of B-Tree Nodes on Flash Storage

Abstract

It is well known that the in-use space in B-tree nodes is only two-thirds, on average. Such low space utilization is detrimental to flash storage in terms of cost as well as performance. In particular, as the database grows, the logical space waste in B-tree nodes will exacerbate the physical write amplification inside flash devices, worsening the write performance and eventually degrading transaction throughput. To address this problem, we propose two space compaction techniques for B-tree nodes: space reservation and data redistribution. The space reservation technique dynamically reserves the free space per index to prevent node split caused by future updates. Meanwhile, data redistribution redistributes records to a neighboring node before the split occurs. Experimental results using MySQL show that our approach can reduce the in-use database space by up to 40%, doubling the throughput. In addition, our approach outperforms MyRocks with less space. Our experimental results confirm that space compaction techniques obsolete on hard disks are very rewarding on flash storage.

Keywords

• B-tree
• flash storage
• space amplification
• space compaction
• write amplification