IPL B+-tree for Flash Memory Database Systems

Abstract

Recently, the in-page logging (IPL) scheme has been proposed to improve the overall write performance of flash memory by avoiding costly erase operations that would be caused by small random write requests common in database applications. In this paper, we identify the problems inherent in the existing design of disk-based B +-tree index, and present the design and implementation of the IPL B +-tree. In this paper, in order to prove the concept of IPL to be a viable and effective solution for flash memory, we show the superior performance of the IPL B +-tree index by running it on a real hardware prototype. We then show the IPL B +-tree index outperforms traditional B +-tree index running on top of an FTL by a factor of two to fifteen. In addition, we introduce the concept of FTL dependency: many existing B + tree schemes for flash memory could not control FTL so that their performance might be heavily dependent on the underlying FTL. In contract, IPL does not suffer from such FTL dependency because it does not assume the underlying FTL.