一种闪存数据库的高更新性能索引结构.pdf

HF-Tree: 一种闪存数据库的高更新性能索引结构 周大 梁智超 孟小峰 ( 中国人民大学信息学院 北京 100872) (cadizhou@) HF-Tree: An Update-Efficient Index for Flash Memory Zhou Da, Liang Zhichao, Meng Xiaofeng (Information school, Renmin University of China, Beijing 100872) Abstract 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, we propose a novel index called HF tree to improve the update performance, which integrates BF F + -tree with Tri-hash. B -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. Our 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. Keywords Flash Memory; Database; Index; Update; Erase 摘要 随着电子技术的发展，闪存作为一种新型的电子存储设备具有高速的访问速度和无机械延迟的特性。但是由于闪存高昂 的写操作代价，传统的基于磁盘的索引结构如果直接应用在闪存上的话会导致极差的更新性能。文中提出一种新颖的索引结构 HF-tree ，通过组提交、更新合并，以及多级延迟的方式来提高更新性能。HF-tree 能够有效地克服闪存和现有基于磁盘索引之间 的不匹配性的问题。通过和经典的BFTL 及 IPL 索引的性能比较，实验结果充分显示了HF-tree 优越的更新和查询性能。此外 HF-tree 能够有效地减少擦除次数，从而延长闪存的使用寿命。 关键词 闪存；数据库；索引；更新；擦除 中图法分类号 TP311