An Efficient B-Tree Using Lazy Update on Flash Memory
Bo-Kyeong Kim, Min-Hee Yoo, Dong-Ho Lee · 2012
Flash memory-based storage systems have been spotlighted as storage devices replacing hard disk drives due to their characteristics such as fast access speed, small size, light weight, and low-power consumption. In contradistinction to the hard disk drive, the flash memory needs an erase operation in addition to a read/write operation, and, the operation unit and time of each operation is asymmetric. Also, since an in-place update is impossible, an erase operation that takes long time precedes an overwrite operation. In order to apply the flash memory to conventional host systems, where read and write operations are only used, an additional intermediate software layer (so-called FTL: Flash Translation Layer) is needed, However, the deployment of a disk-based B-tree on FTL as an index structure causes performance degradation due to its intensive in-place updates. Therefore, a novel index structure considering the characteristics of the flash memory is needed. Although -Tree and LSB-Tree are proposed as flash-aware index structures, -Tree suffers from inefficient page management and LSB-Tree also has additional management cost of temporary nodes. We propose a B-tree index structure using lazy update on flash memory to solve these problems of -Tree and LSB-Tree. Our proposed index structure enhances search and write performances because it delays the node update by storing the node to be updated in main memory when the record is inserted. It also supports the sequential insertion without split operations. Through a mathematical analysis and experimental results, we show that our proposed index structure yields better performance than -Tree and LSB-Tree.