¡@
Journal of Information Science and Engineering, Vol. 27 No.
1, pp. 111-127 (January 2011)
IPL B+-tree for Flash Memory Database Systems*
GAP-JOO NA, BONGKI MOON+ AND SANG-WON LEE
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
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.