随着嵌入式导航系统应用的日益广泛,人们对于使用嵌入式导航系统产品的需求也日益旺盛,其市场也在不断扩大。伴随着我国自行研制的北斗卫星导航系统进入新的发展建设阶段,中国自主导航系统也更加成熟,因此对嵌入式导航系统的研究价值也在不断扩大。路径规划是嵌入式导航系统中的重要组成部分,其路网数据的索引存储和路径数据检索算法的选取是影响效率和最优性的两个特点。由于目前交通路网复杂程度的不断扩大和三维电子地图的出现,直接导致了路径规划数据量的质变,因数据量的质变使得难以将所有路径数据一次性地从外存读入内存并服务于路径规划算法,这同时也导致路径数据检索算法的搜索场所将处于外存介质中(如SD卡)。以往的路径数据检索一般都假定被规划的路径数据在内存中是作为一个整体来考虑的,这给传统的数据检索和规划算法对于海量外存数据而言带来了不适应且低效率的问题。因此,在对路径数据外存索引存储的新要求下,本文从路径数据存储组织方式和搜索场所角度出发,为快速检索路径规划数据而研究的路网数据索引存储是本文的研究重点。　　 基于上述问题,本文主要研究面向外存并基于导航路径寻优的地图数据库分层索引机理,重点包括以下几个方面:　　 (1)通过组织海量地图路网数据于外存SD卡中,针对路径规划数据的快速检索而研究设计新的HRN(Hierarchical road network,路网分层)模型,并进一步优化其分层拓扑结构。　　 (2)以HRN模型为基础,研究一种新的针对外存SD卡中最低层实体数据同其他各层数据的有效组织映射方式来达到数据紧缩存储以及便于路径数据检索的目的。　　 (3)为提高以限制SD卡中数据量加载为前提的路径数据检索算法的效率,研究并提出以G-SDBCScan(Geospatial Database Convergence Scan,地理空间数据库收敛扫描)算法为基础的路径数据分层索引来适应其数据存储方式和搜索场所的改变。　　 (4)通过嵌入式数据库在分层索引存储设计及数据检索中的合理应用,验证本文分层索引机制的适应性。　　 最后,本文以嵌入式Linux操作系统及QT/Embeded作为研究实验平台,通过新的路径规划数据检索算法,实现海量数据静态路径规划,并验证针对海量外存路径数据的分层索引存储的有效性。