Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]


Journal of Information Science and Engineering, Vol. 27 No. 1, pp. 111-127 (January 2011)

IPL B+-tree for Flash Memory Database Systems*

School of Information and Communication Engineering
Sungkyunkwan University
Suwon, 440-746 Korea
+Department of Computer Science
University of Arizona
Tucson, AZ 8572, U.S.A.

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.

Keywords: flash memory, database, B+-tree, FTL, index structure

Full Text () Retrieve PDF document (201101_08.pdf)

Received July 7, 2009; revised September 15 & December 18, 2009; accepted March 8, 2010.
Communicated by Tei-Wei Kuo.
* This research was partly supported by MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008) and by MEST, Korea under NRF Grants No. 2010-0025649 and 2010-0026511. This work was also sponsored in part by the U.S. National Science Foundation Grant IIS-0848503. The authors assume all responsibility for the contents of the paper.