FlashB-tree: A novel B-tree index scheme for solid state drives

Solid State Drive (SSD) is rapidly deployed as data storage for embedded and tablet computers 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 characteristics, the hard disk drive (HDD)-based systems and applications could hardly make full use of the advantages of SSD when directly adopting themselves on it. In addition, the frequent changes of B-tree can degrade the performance of SSD and reduce the service life. Most previous works have been battling these thorny problems and improved the performance to some extent. In this paper, we first analyze two existing mechanisms which are suitable to write-intensive and read-intensive workloads, respectively. And we pointed out the drawbacks of them. As a solution, we propose a novel B-tree index implementation scheme, a FlashB-tree, which eliminates the number of reorganizing of the tree structure. And we adopt Online Transition Algorithm for utilizing the superiority of two representative mechanisms. With several indexing profiles having different mixture of insert, select and delete operations of indices, we measured the access time performance, it is sure that the proposed methodology could significantly enhance the efficiency of using index on SSDs.