基于NANDFlash的嵌入式GIS地图格式设计及优化

论文摘要

随着嵌入式计算的不断发展,NAND作为一种高效的存储设备越来越多的被运用到嵌入式环境中,由于各种硬件和软件性能的不断提高使得GIS也得以在嵌入式环境中得到广泛运用。GIS中决定查询性能的是地图空间数据的索引方式,目前普遍采用的是基于磁盘的R-Tree变种索引,本文在此基础上提出了一种更高效的R-Tree变种索引Rd-Tree,并根据NAND Flash的读写特性对索引树的更新方式做出优化。本文的主要工作包括以下两点:（1）在分析Ro-Tree的基础上,提出了一种新的索引结构Rd-Tree。Ro-Tree提出了外部节点的概念,就是将节点中离其它孩子节点都比较远的孩子作为外部节点,然后放到上一级节点中,藉此来优化节点的质量,减少节点之间的重叠区域。Rd-Tree是一种基于节点密度的索引结构,节点密度是衡量节点性质的一个指标,Rd-Tree的核心思想就是将密度相近的点组织在一起,而在现实世界中,这些密度相近的节点往往在物理上也是相近的。Rd-Tree在以下几方面对Ro-Tree做了改进:一是改进了插入过程中对外部节点的识别算法,在Rd-Tree中如果将一个子节点插入父节点后并不引起父节点密度的降低,我们认为该节点并不是一个外部节点,该识别算法不仅从逻辑上更契合外部节点定义而且优化了节点的质量,减少了节点中的外部节点数量;二是优化了删除过程,当在删除过程中节点向下溢出时,通过从父节点借入一个外部节点来防止无意义的重新插入;三是提高了查询效率,由于减少了外部节点数量,因此在查询过程中需要比较的次数也会相应减少,对于经典的区域查询,对比Ro-Tree本文在实验部分获得了20%的效率提高。（2）根据NAND Flash的物理特性引入了日志更新机制。由于NAND是一种write-once设备,直接在原文件上进行更新操作会在NAND中产生大量的垃圾数据,降低NAND使用空间进而导致垃圾回收时的频繁擦除操作。因此本文将地图数据分为源数据文件和更新数据文件,将地图的更新以日志的形式全部追加到更新数据文件的尾部,每次打开地图时,将更新数据提交到源数据上,在内存中生成一棵新的索引树。考虑到效率,本文还研究了地图的紧缩操作,即当更新数据比较多的时候地图重建过程会比较长,将更新提交后的新索引树写回到NAND作为新的源数据文件,并删除更新数据文件。本文对地图紧缩的时机也做了探讨。通过本文的研究,使得对空间数据的索引更高效,对NAND的使用更加优化,延长了NAND的使用寿命并减少了文件系统的垃圾回收次数。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 嵌入式 GIS 的发展
• 1.1.2 Nand Flash 的广泛应用
• 1.1.3 目前地图格式的不足
• 1.2 本文的研究目标及内容
• 1.3 本文的主要结构
• 1.4 本章小结
• 第二章 关键技术
• 2.1 通用空间数据索引
• 2.1.1 K-D 树
• 2.1.2 Quad Tree
• 2.1.3 R-Tree
• *-Tree'>2.1.4 R^*-Tree
• o-Tree'>2.1.5 R^o-Tree
• 2.1.6 Hilbert R-Tree
• 2.2 文件系统对 Flash 文件的处理与优化
• 2.2.1 Nand Flash 的物理结构
• 2.2.2 Nand 读写特性
• 2.2.3 FTL 及其作用
• 2.2.4 Yaffs2 对 Flash 的优化
• 2.3 本章小结
• 第三章 地图格式设计与实现
• d‐Tree'>3.1 新的索引结构 R^d‐Tree
• 3.2 新的更新机制日志更新
• 3.3 地图的存储结构
• 3.4 地图的重建过程
• 3.5 地图的紧缩
• 3.6 关键数据结构
• 3.6.1 内存索引结构
• 3.6.2 NAND 索引结构
• 3.6.3 更新项数据结构
• 3.7 地图操作实现
• 3.7.1 插入图元
• 3.7.2 修改图元
• 3.7.3 删除图元
• 3.7.4 地图的重建过程
• 3.7.5 地图的紧缩
• 3.8 本章小结
• 第四章 地图格式优化效率验证
• 4.1 构建试验环境
• 4.2 试验流程
• 4.2.1 修改 yaffs2
• 4.2.2 生成地图数据
• d-Tree'>4.2.3 验证 R^d-Tree
• 4.2.4 验证新的更新方式
• 4.2.5 输出实验数据
• 4.3 试验结果分析与小结
• 4.3.1 索引树比较结果
• 4.3.2 更新方式比较结果
• 4.3.3 实验小结
• 4.4 地图格式应用
• 第五章 结束语
• 参考文献
• 致谢
• 攻读硕士学位期间已发表或录用的论文