  This paper studies the design of B-tree that can take full advantage of
modern storage hardware with built-in transparent compression. Recent years
have witnessed significant interest in applying log-structured merge tree
(LSM-tree) as an alternative to B-tree. The current consensus is that, compared
with B-tree, LSM-tree has distinct advantages in terms of storage space
efficiency and write amplification. This paper argues that one should revisit
this belief upon the arrival of storage hardware with built-in transparent
compression. Advanced storage appliances~(e.g., all-flash array) and emerging
computational storage drives perform hardware-based lossless data compression,
transparent to OS and user applications. Beyond straightforwardly reducing the
physical storage cost difference between B-tree and LSM-tree, such modern
storage hardware brings new opportunities to innovate B-tree implementation in
order to largely reduce its write amplification. As the first step to explore
the potential, this paper presents three simple design techniques (i.e.,
deterministic page shadowing, localized page modification logging, and sparse
redo logging) that can leverage such modern storage hardware to significantly
reduce the B-tree write amplification. We implemented these design techniques
and carried out experiments on a commercial storage drive with built-in
transparent compression. The results show that the proposed design techniques
can reduce the B-tree write amplification by over 10x. Compared with RocksDB (a
popular key-value store built upon LSM-tree), the implemented B-tree can
achieve similar or even smaller write amplification and physical storage space
usage.

Databases