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