第三讲(GIS第四讲).ppt

6.4 空间数据索引 空间索引的层次结构 无缝图层 工作区索引 目标索引 窗坐标、BSP、KDB树、R树和R+树、CELL树 1、空间数据索引的必要性 在GIS中需要根据空间位置进行查询，例如，“找出通过某个区域的所有公路”，“检索在某个区域内的所有湖泊”等等。 为了处理这类空间查询，数据库需要检查每一个可能满足条件的空间要素的记录，看它是否与查询区域相交或是在查询区域内，这种空间相交运算需要先读出空间要素几何形状的边界坐标，然后再与空间区域进行空间关系运算。 由于传统数据库的这种穷尽式有哪些信誉好的足球投注网站方法花费的磁盘访问时间和空间运算时间都很长，往往达到令人无法忍受的程度，故必须建立空间数据索引机制。 2、空间索引的层次 3、无缝图层 现实世界的地区、城市均是连续的。 对较小的区域可以将数据物理连接，生成物理无缝图层。 对无法生成物理无缝图层的地区，可以建立逻辑无缝图层。 逻辑无缝图层建立了地物的连接描述。 4、工作区索引 对海量数据而言，必须建立多个工作区，将数据按工作区存放于存储器 建立索引文件 在开窗操作时，系统根据窗口坐标，按索引文件迅速调入所涉及的工作区 5、目标索引 窗坐标索引机制 格网型空间索引 BSP索引机制 KDB树 R树和R+树 CELL树 6、窗坐标索引机制 建立每个实体的最小包容矩形，记录其对角坐标。单点检索可判断是否在包容矩形内；范围检索可判断每个实体的最小包容矩形和范围的关系：内、外、相交。 对所有空间实体的外接矩形最大最小坐标进行落入判别，其中空间实体B、C完全落入查询窗，从空间数据库中提取B和C的相应数据。 7、格网型空间索引 将区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。进行空间查询时，首先计算出查询对象所在格网，然后再在该网格中快速查询所选空间实体。 一条河流、一个湖泊和一条省界，它们的关键字分别为5，11和23。河流穿过的栅格为2，34，35，67，68；湖泊覆盖的栅格为68，69，100，101；省界所通过的栅格为5，37，36，35，67，99，98，97。 8、BSP索引机制 是一种二叉树，它将空间逐级进行一分为二的划分。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。 9、KDB树 KDB树是B树向多维空间的一种发展。它对于多维空间中的点进行索引具有较好的动态特性，删除和增加空间点对象也可以很方便地实现； 其缺点是不直接支持占据一定空间范围的地物要素，如二维空间中的线和面。该缺点可以通过空间映射或变换的方法部分地得到解决。 10、R 树示意图 上图表示了三组多边形（矩形，用实线画出）及对应于这三组多边形的R树中结点的外包络矩形（用虚线画出），右图为R树本身。 11、R+树结构示意图 R+树的数据结构与R树的相同，但是，对于被分割的下层虚拟矩形或实体外接矩形，还要增加关系表达： 原矩形标识符，分割后矩形1的标识符，分割后矩形2的标识符 12、R树和R+树比较 由于R树兄弟结点对应的空间区域可以重叠，因此，R树可以较容易地进行插入和删除操作；但正因为区域之间有重叠，空间索引可能要对多条路径进行有哪些信誉好的足球投注网站后才能得到最后的结果，因此，其空间有哪些信誉好的足球投注网站的效率较低。 在R+树中，兄弟结点对应的空间区域没有重叠，而没有重叠的区域划分可以使空间索引有哪些信誉好的足球投注网站的速度大大提高；但由于在插入和删除空间对象时要保证兄弟结点对应的空间区域不重叠，而使插入和删除操作的效率降低。 13、CELL树 R树和R+在插入、删除和空间有哪些信誉好的足球投注网站效率两方面难于兼顾，故CELL树应运而生。它在采用凸多边形来作为划分的基本单位，与BSP树有类似之处，子空间不再相互覆盖。故CELL树是比较优秀的空间索引方法。 6.5 空间数据模型 三种传统模型 层次、网络、关系 面向对象模型 二维矢量模型 栅格数据模型 三维空间模型 矢量、栅格 一、三种传统模型 层次 网络 关系 1、层次模型 2、层次模型描述矢量数据 特点是将数据组织成一对多关系的结构。 层次结构采用关键字来访问其中每一层次的每一部分。 层次数据库结构特别适用于文献目录、土壤分类、部门机构等分级数据的组织 3、层次数据的特点 优点： 存取方便且速度快 结构清晰，容易理解 数据修改和数据库扩展容易实现 检索关键属性十分方便 缺陷： 结构呆板，缺乏灵活性 同一属性数据要存储多次，数据冗余大（如公共边） 不适合于拓扑空间数据的组织 4、空间对象的层次分类编码 分类对象的从属和层次关系 有明确的分类对象类别和严格的隶属关系 5、网络模型 6、用网络数据模型描述复杂关系 网络模型用连接指令或指针来确定数据间的显式连接关系，是具有多对多类型的数据组织方式