HF-Tree:一种闪存数据库的高更新性能索引结构

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

随着电子技术的发展,闪存作为一种新型的电子存储设备具有高速的访问速度和无机械延迟的特性.但是由于闪存高昂的写操作代价,传统的基于磁盘的索引结构如果直接应用在闪存上会导致极差的更新性能.提出一种新颖的索引结构HF-Tree,通过组提交、更新合并以及多级延迟的方式来提高更新性能.HF-Tree能够有效地克服闪存和现有基于磁盘索引之间的不匹配性的问题.通过和经典的BFTL及IPL索引的性能比较,实验结果充分显示了HF-Tree优越的更新和查询性能.此外HF-Tree能够有效地减少擦除次数,从而延长闪存的使用寿命.

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.