文档介绍：硕士学位论文
支持频繁更新的 Flash 存储管理技术研究
RESEARCH ON THE FLASH STORAGE
MANAGEMENT TECHNIQUE FOR
THE UPDATEINTENSIVE ENVIRONMENT
罗永明
哈尔滨工业大学
2009 年 6 月
国内图书分类号: 学校代码:10213
国际图书分类号: 密级:公开
工学硕士学位论文
支持频繁更新的 Flash 存储管理技术研究
硕士研究生: 罗永明
导师: 李建中教授
申请学位级别: 工学硕士
学科、专业: 计算机科学与技术
所在单位: 计算机科学与技术学院
答辩日期: 2009 年 6 月
授予学位单位: 哈尔滨工业大学
Classified Index:
:
Dissertation for the Master Degree in Engineering.
RESEARCH ON THE FLASH STORAGE
MANAGEMENT TECHNIQUE FOR
THE UPDATEINTENSIVE ENVIRONMENT
Candidate: LuoYongming
Supervisor: ProfessorLi Jianzhong
Academic Degree Applied for: Master of Engineering
Speciality: ComputerScience and Technology
Affiliation: School puter Science and
Technology
Date of Defence: June, 2009
Degree-Conferring-Institution: Harbin Instituteof Technology
:
哈尔滨工业大学工学硕士学位论文
摘要
随着 Flash 产业的发展与成熟, Flash 存储器作为一种新的存储介质已经
被广泛应用到计算机系统中,并有全面取代磁盘的趋势。由于与传统磁盘的读
写特性不同, Flash 存储器上的数据管理问题近期成为数据库领域的研究热
点。本文集中探讨在数据频繁更新环境下 Flash 存储器上的数据管理问题。
本文提出一种称为 FBX-Tree 的索引结构。该结构在逻辑上提供与 B-Tree
相同的接口,在实际操作文件时将所有对文件的内部更新操作转化为对文件的
追加操作,充分利用了 Flash 存储器随机访问文件块较快、更新内部文件块较
慢的特点,使系统性能获得提升。 FBX-Tree 中的每个叶子节点都在内存中对
应一个文件块指针链表,链表长度影响了查询性能,因此需要在适当时刻对其
进行整理。我们将决策整理链表时机的问题进行了形式化定义,提出三种近
似 on-line 算法对其进行处理, 并证明了它们的近似比分别为 K 、 3 和
K 1
+ ,其中 K 为算法给定的阈值。
2 3
为说明 FBX-Tree 的使用方法,本文应用其解决移动对象的查询处理问
题。本文提出一种基于 FBX-Tree 的移动对象索引方法,该方法使用 FBX-Tree
作为后端存储结构,使用 Bx-Tree 作为前端查询处理方法,支持区域查询、 K
近邻查询和持续区域查询。三种查询操作均对 FBX-Tree 做了优化。
基于上述方法本文进行了大量的实验。理论分析和实验结果表明, FBX-
Tree 在系统吞吐率和查询性能上均较以往方法有较大改善,并在内存与外存
的空间占用上取得了平衡,延长了器件寿命。
关键词:Flash 存储器;存储系统;时空索引;移动对象数据库
-I-
哈尔滨工业大学工学硕士学位论文
Abstract
With the advance in flash industry, as a new type of storage device, flash
memory has e widly used puter system, and will totally replace the
ic disks in the near future. Because of its different I/O pattern, the data
management issues over flash disk e a hot spot in database research. This
paper mainly focuses on the data managemen