Improving Search Performance of B-tree on Flash Devices
Flash memory comes with some challenges like write endurance and write amplifications. In this work, we explore a new perspective in implementing B-trees on flash. Previous works have predominantly focused on improving the insert performance, while we consider ways to improves search performance. We propose a novel technique to partition and store newly inserted data and a complimentary concept of metadata to speed up the search performance. The metadata exploits the incremental 1-to-0 update properties of flash in interesting ways to conserve the page invalidations. Our experiments revealed 60% search response time improvement over the best of the alternative schemes.
Keywords - B+-Tree, Index Structure, Endurance, Flash-Memory, SSD, Storage Systems