LSB-tree : B-tree for NAND flash memory

LSB-Tree: A Log-Structured B-Tree for Flash Memory-based Solid State Drives

A solid state drive (SSD) has been popularly used because of its high access speed, low power consumption, and high reliability. Flash memory-based SSDs consist of NAND flash memories and inherit the physical characteristics of a NAND flash memory. However, due to unique characteristics of the flash memory such as erase-before-write architecture and asymmetric operation speed/unit, conventional disk-based systems and applications may experience severe performance degradation on SSDs. When a B-Tree is implemented on SSDs, intensive overwrite operations, which are caused by record inserting, deleting, and reorganizing, may result in severe performance degradation. Although several index structures have been proposed in order to overcome this problem, they suffer from frequent node split, rapid increment of the tree height, poor page utilization, and etc.

In this research, we had proposed a Log-Structured B-Tree (LSB-Tree) where a log node corresponding to a leaf node is allocated for updating the modified data and then these data inthe log node is stored in a single write operation. LSB-Tree reduces additional write operations by deferring the change of the parent nodes. Also, it reduces the number of write operations by directly switching the log node to a leaf node if the data are sequentially inserted according to the key order. Through various experiments, we show that LSB-Tree performs better than related techniques.

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 항목은 *(으)로 표시합니다