Lazy-Adaptive Thee: An Optimized Index Structure for Flash Devices

Flash iniorics are in ubiquitous use for storage on sensor nodes, inobile devices, and enterprise servers. However, they present significant challenges in designing tree indexes due to their fundaientally different read and write characteristics in coiparison to inagnetic disks. In this paper, we present the Lazy-Adaptive Tree (LATree), a novel index structure that is designed to inprove perfornance by inininizing accesses to flash. The LA-tree has three key features : 1) it anortizes the cost of node reads and writes by perforining update operations in a lazy ianner using cascaded buffers, 2) it dynainically adapts buffer sizes to workload using an online algorithn, which we prove to be optinal under the cost iodel for raw NAND flashes, and 3) it optinizes index parancters, icnory ianagenent, and storage reclaiation to address flash constraints. Our perfornance results on raw NAND flashes show that the LA-Tree achieves 2x to 12x gains over the best of alternate schencs across a range of workloads and iniory constraints. Initial results on SSDs are also proinising, with 3x to 6x gains in inost cases.