HF-Tree: An Update-Efficient Index for Flash Memory

With the recent development of electronic technologies,flash memory emerges as new data storage media with high access speed and no mechanical latency.Flash memory drives have been envisioned to be widely used in laptops,desktops,and data servers in place of hard disks in the years to come.However,due to the expensive write cost of flash memory,traditional disk-based indexes have a poor update performance when directly applied to flash drives.In this paper,the authors propose a novel index called HF-tree to improve the update performance,which integrates BF-Tree with Tri-Hash.BF-Tree is adapted from the traditional B+-Tree,yet it avoids excessive updates of B+-Tree by adopting a block-based storage model and a lazy split and coalesce algorithm.Tri-Hash uses three cascaded hash structures to reduce update costs by gracefully deferring and grouping writes in main memory and flash memory.The HF-Tree index addresses the gap between access characteristics of flash memory and disk-based indexes.Performance evaluation against the existing BFTL and IPL methods shows superior update and query performance of the proposed HF-tree index.Moreover,the HF-tree index incurs less erase operations and extends the lifetime of flash memory.