An efficient index buffer management scheme for implementing a B-tree on NAND flash memory

Recently, NAND flash memory has been one of the best storage mediums for various embedded systems such as MP3 players, mobile phones and laptops because of its shock-resistant, low-power consumption, and none-volatile properties. However, since it has very distinct characteristics including erase-before-write and asymmetric read/write speed, the performance of disk based systems and applications may degrade dramatically when directly adopting them on the flash memory storage systems. Especially when a B-tree is constructed on NAND flash memory, intensive overwrite operations may be caused by record inserting, deleting, and reorganizing. These may result in severe performance degradation when building the B-tree. In this paper, we propose an efficient index buffer management scheme, called IBSF, which eliminates redundant index units in the index buffer and then delays the time that the index buffer requires to become full. Consequently, IBSF significantly reduces the number of write operations to a flash memory when constructing a B-tree. We also show that IBSF yields a better performance on a flash memory by comparing it to the related technique through various experiments. (C) 2010 Elsevier B.V. All rights reserved.