The FD-tree Reexamined: A Case For Indexing Flash Database

The flash storage is widely considered as a next-generation permanent storage media which will replace magnetic disk in database systems because of its high random read, low power consumption and silence. Consequently, the existing DBMS technique, for example, B+ tree index, needs revolution to fit the new characterizes of the flash media. Because tree like indices are key method of accessing data in flash-based DBMS and have a significant impact on query performance of flash-based DBMS, a lot of research work has been carried out in this area. FD-tree, a tree like index specially designed for flash storage, improves the performance on flash storage via converting the random writing to the bulk sequential writing.However, FD-tree also has very obvious shortcomings when applied to practical flash-based DBMS. When the FD-tree initializes, a large amount of writing operations are produced during the merge of neighbor levels, which degrades the system performance. In this paper, we propose a novel algorithm to populate large data into FD-Tree. Specifically, we divide the merge operation of a whole level to different ranges, reducing the number of I/Os. We prove that the complexity of our algorithm is O(n log n), in which n is the number of data items. Experiments on a real flash disk demonstrate that our algorithm outperforms the conventional insert-based method in both I/O times and CPU clocks.As each level of FD-tree is sorted index pages, it is very suitable for data compression. In this paper we provide an algorithm to compress the index entries (including key, type and rowid) on each page of FD-tree. Our algorithm reaches a remarkable compression ratio and better query improvement while remains the same complexity as before. The TPC-H 1GB index data test shows that our algorithm can save a half storage required and brings 20% to 40% query performance improvement.