Research On Hybrid Index Structure For Flash Disks

Flash memory is a new novel solid-state storage medium and first appeared in 1980s. Flash memory has some superior features, such as high speed, shock resistance, low power consumption, and small size. Flas memory is a pure electrical device, and then it can overcome drawback caused by the mechanical moving part in magnetic disks. In recent years, flash memory is widely used, it not be limited in the embedded systems and portable devices, but a new important secondary storage device (SSD, soild state drive), and has been applied in enterprise computing environment.The rapid increase of fabrication technology leads to increasing of capacity and decreasing of price, which speeds up the replacement of magnetic disk with SSD as a new secondary storage drive.Managing data with database is a widely used technique, and with the widely used of SSD as storage devices, the DBMS will be migrated to SSD ineluctability. But due to the distinct characteristics of SSD, directly transplanting traditional magnetic disk based database technique to SSD could not fully play the performance advantages of flash memory. In some situation, the performance even poor than magnetic disk. Therefore, researching on the problems in flash-based DBMS has important theoretic significance and value.SSD, which is flash packaged in HDD form factors and capable of working with device drivers and I/O buses designed for HDDs, also has some superior features then magnetic disk, such as extremely fast random read speed and low power consumption. Therefore, SSD is much more suitable to be secondary storage device than magnetic disk. In this paper, we will mainly discuss SSD-optimized index structure.Traditional index structures do not take the flash I/O characteristics into account and, therefore, will cause poor performance. To address this problem, we present a new hybrid index structure for flash disks in this paper, which is called HashTree. HashTree aims at getting better update performance while keeping relatively high search efficiency.The main contributions of the paper are summarized as follows:(1) We propose a hybrid index structure for flash disks, called HashTree.(2) We introduce a tuning mechanism into the HashTree so that we can obtain appropriate trade-off between search performance and update performance.(3) We discuss strategy to get optimal performance over different SSDs.