A group round robin based B-tree index storage scheme for flash memory devices

Flash memory is rapidly deployed as data storage for embedded and tablet PCs due to its shock resistance, fast access, and low power consumption. However, it has some intractable characteristics such as erase-before-write, asymmetric read/write/erase speed, and limited number of write/erase cycles. Due to these hardware limitations, the magnetic disk-based systems and applications could hardly make full use of the advantages of flash memory when directly adopting themselves on it. For example, the frequent changes of B-tree can degrade the storage performance of flash memory. Most of the recent studies on flash-aware index design focused mainly on the buffer management scheme whereby they can reduce the costly write operations to flash. However, in this paper, we present a novel B-tree storage scheme, a group round robin based B-tree index storage scheme, which applies a dynamic grouping and round robin techniques for erase-minimized storage of B-tree in flash memory under heavy-update workload. Experiment results show that the proposed scheme is efficient for frequently changed B-tree structure and improves the I/O performance by 2.14X at best, compared to the related work.