目前，绝大部分嵌入式设备使用的电子地图都是二维的。二维的电子地图不能够形象、生动、直观地反应三维世界，且在表达立体空间层次复杂的地理信息时比较困难，如多层立交桥等。随着计算机软、硬件技术的发展，三维电子地图应运而生，它在一些性能强大的PC机上已见应用。由于嵌入式设备的存储空间相对较小和处理速度相对较慢等硬件条件的限制，在嵌入式设备上应用三维电子地图还比较少见，但是由于嵌入式设备的移动性好，运行于嵌入式设备上的三维电子地图必将迅速发展。三维电子地图的数据主要包括用于显示的三维场景数据和用于路径寻优的三维路径规划数据等。由于自然景观非常多、人工道路网和其它建筑物的逐年剧增，嵌入式设备不可能将所有数据一次加载进入内存，因此三维电子地图的数据量相对于嵌入式系统的内存而言是“海量的”，外存中数据的组织和检索方法成为了影响整个嵌入式系统的重要因素。传统的电子导航系统一般一次加载所有可能用到的地图数据入内存，然后进行相关的操作，而对于海量的三维电子地图数据，以往的这些地图数据组织和检索的方法基本不太实用了，难以实现快速路径寻优和流畅的三维场景显示在嵌入式设备上同时满足，故嵌入式系统中的三维场景数据和路径规划数据的外存组织和检索方法成为了本文的研究重点。本文分别从场景数据和路径规划数据的外存组织与索引两方面进行了研究，主要做了如下工作：1．对海量的三维场景数据，本文先将地图进行分块，划分成为平面面积相等的规则小场景，然后对每个小场景使用改进的八叉树进行场景空间剖分，接着利用三维的Hilbert曲线对场景中八叉树节点进行线性编码并进行优化，最后将每个节点及其中的数据按照编码顺序存于外存之中。实验结果表明：由于嵌入式系统可以选择性地调入需要的场景数据、无需动态地建立场景的内存管理索引结构且节点及其中数据存储的高聚类性，三维场景的外存检索速度得到了提升，显示和漫游的速度得到了加快。2．本文提出了一种改进的八叉树，弥补了传统的八叉树忽略了实体的整体性和面向对象的八叉树对于三角面多而实体对象较少的场景难于构建的不足。3．对于海量的三维路径规划数据，本文在分层结合分块的组织方法基础上，针对传统组织方法数据冗余多、不符合人们选择路径的习惯和确定路径权值慢等问题，结合行政区域管理特点、道路的质量、交通和地理分布等因素，提出了对每层的路径数据先按照行政区域进行划分，然后利用多边形对路网进行分块的组织方法，最后利用改进的K均值聚类法为分块路网建立了带聚类的Hilbert R-树索引，提高了外存检索的效率，减少了外存的I/O次数和路径寻优的时间。4．最后，以Android为平台，利用SQLite数据库验证了本文提出的三维电子地图数据外存组织和检索方法的有效性。