文档介绍：上海交通大学
硕士学位论文
基于NAND Flash的嵌入式GIS地图格式设计及优化
姓名:蔡松露
申请学位级别:硕士
专业:计算机应用技术
指导教师:步丰林;戚正伟
20091201
基于 NAND Flash 的嵌入式 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 作为新的
IV
源数据文件,并删除更新数据文件。本文对地图紧缩的时机也做了探
讨。
通过本文的研究,使得对空间数据的索引更高效,对 NAND 的使用
更加优化,延长了 NAND 的使用寿命并减少了文件系统的垃圾回收次
数。

关键词:NAND、 Ro 树、Rd 树、地理信息系统、日志更新
V
Design & Optimization of Embedded GIS based on Nand Flash

ABSTRACT

With development of puting, NAND is pervasive in this
environment as an efficient storage device. Benefiting from the enhancement
of hardware & software performance, GIS is popular in the Embedded
platform. In GIS, the performance is mostly determined by the index structure
of space data, and now the general index structure is variants of R-Tree based
on hard disk. This paper introduces a more efficient variants of R-Tree, and
do some optimization works directed towards unique Read & Write feature of
NAND Flash.
This paper include