文档介绍：华中科技大学
硕士学位论文
基于闪存的嵌入式数据库索引技术设计与实现
姓名:项磊
申请学位级别:硕士
专业:通信与信息系统
指导教师:黄本雄
20090501
华中科技大学硕士学位论文
摘要
随着嵌入式系统的不断完善和发展,应用终端对数据的存取能力提出了更高的要
求,因此有必要使用数据库管理系统。由于 NAND 闪存的优良特性,目前大多数嵌
入式系统它作为存储介质。但是不同于传统磁盘,往 NAND 闪存中写入数据时,不
能在原来数据的基础之上覆盖而是必须在已经执行了擦除操作的区块中进行,对各
个区块执行擦除操作的次数是有限制的。而数据库的写操作发生次数是很多的,从
而导致了擦除操作的增多,减短了 NAND 闪存使用期限。怎么克服 NAND 闪存这
一特性是一直备受关注的问题。
B+树数据库索引在数据读写等方面的性能有着较大的优势,可移植性强,有较好
的稳定性和可维护性。在数据库实际应用中,索引的写入次数是很多的,这对 NAND
闪存使用期限会产生影响,因此需要设计一种针对 NAND 闪存物理特性的索引机制,
尽量减少对 NAND 闪存的写入和擦除操作。
在分析 NAND 闪存和嵌入式数据库的基础上,首先结合“附加页”和 B+树索引,
在结点将要分裂时,使用“附加页”来存储插入的新的关键字,有效地缓解了分裂
操作,从而减少了对 NAND 闪存的写入和擦除,并且提高了数据存储率;其次结合
日志文件系统思想,采用 Log-Mode 的 B+树索引机制,跟随结点的变化,将变化的
内容记入到日志。每一次写操作对应一条 Log Entry,当待写入到数据库的数据记录
占满系统开设的记录缓冲区时,对应的日志记录就被写到 NAND 闪存中。建立一个
B+树结点构架图,并用结点对应的日志记录地址链表(NLAT)把结点与结点对应的
日志记录联系起来。Log-Mode 索引树合并了大量写入操作,减少了对 NAND 闪存
的擦写,延长了闪存使用期限。对 NLAT 中链表长度通过“压缩”日志记录进行了
控制从而提高了系统读性能,并且对读写性能进行了分析。对“过时”的日志记录
进行清理,结合实际应用提出了一种平衡磨损算法,均衡地使用 NAND 闪存的各个
区块,从而延长闪存使用期限。最后搭建实验平台,在嵌入式 Linux 系统中,将改
进后的索引应用到 SQLite3 嵌入式数据库中,对比测试各数据指标,结果表明改进
后的方案有效地使闪存得以长久使用,同时也提高了数据存储占有率。

关键词:NAND 闪存;B++树索引;日志记录;平衡磨损;擦除操作
I
华中科技大学硕士学位论文
Abstract
With the development of embedded system, application terminal’s demand on the
storage and management system of data is enhanced accordingly,as a result we have to use
database management NAND Flash is selected as storage medium in
most embedded system,as its attractive features such as high accessing speed,low consume
and small Flash is widely used in embedded NAND Flash has
its shortage,the way of writing on NAND flash isn’t covering the old data,and we can only
write on the block which has been erased. If there is some invalid data in a block,the block
will be erased when there isn’t enough free block can’t be erased endlessly,and
the maximum erasure times of each block is writing operations are very
frequent in the