空间索引结构(学生)

《空间索引结构(学生)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第七章空间索引结构空间索引技术是从空间数据库中获取空间数据的宥效方法，是提高空间数据查询和各种空间分析效率的关键技术。建立空间索引是为了缩小空间数据的搜索范W，以便在空间数据查询吋不必遍历整个空间数据集，只访问空间索引数据便可快速得到一条特定的空间查询语句所请求的空间数据，或得到包含全部空间查询结果的一个较小的空间数据集。索引文件中包含的数据称为索引数据，索引结构是索引数据的数据结构及索引创建与维护算法的总称。空间索川结构是按照空间数据在空间分布上的特性来组织和存储索引数据的索引结构。一种良好的空间索引结构应满

2、足下列三个要求：一、存储效率高：相对于被索引的数据集而言，索引数据的数据量应尽量小。否则，访问索引数据可能成为数据查询与更新的效率瓶颈。二、查询效率高：空间索引结构需要选择良好的索引数据结构，设计具体的基于索引的空间访问方法（SAMSpatialAccessMethod）,必须能够高效的交现以下几种基丁•位置的查询：1、点选择：从数据集中找出包含给定点的所宥空间对象。2、范围查询：查询与给定对象间的距离小于某个给定值的所宥空间对象。3、区域（窗口）查询：查找含在区域内、与区域相交或部分位于区域中的所有空间对象。

3、窗口是一个特殊的区域，窗口查询是GIS屮最常用、最基本的查询。4、K-最邻近查询：给定一个参照对象（点、线或区域），査询距离参照对象最近的K2I个空间对象。5、空间关系查询：相交、相邻、包含等拓扑关系査询，方位关系和基于距离的各种查询。6、其他查询：将满足一定空间条件的两个空间对象集合进行空间连接，空间集合运算等也是一种空间访问。三、更新效率高：许多GIS应用中会涉及海量且不断变化的空间数据集。数据集中数据对象的增加、修改和删除将直接导致索引数据的更新，索引数据与被索引的数据集必须保持一致，冰能保证基于索引数据

4、的查询结果的正确性。索引数据的吏新操作包括：插入索引项，将新数据对象的索引项添加到索引数据屮；删除索引项，把数据对象的索引项从索W数据屮删除；修改索引项，在索引数据中先删除再增加该数据对象的索引。数据集经常变化时，要求其索引数据的更新开销不要很大，特别耍避免更新时w起的索引重组。a此，需耍考虑新增索4项和删除索引项时，索引结构的快速更新能力。很难设计一种空问索引结构同时能够提供高效的存储、高效的查询和高效的更新，实际应用中总是牺牲某些方面的效率來换取另外方面的效率。索引结构可分为静态索引和动态索引结构。静态索引

5、结构针对静态不变的数裾，索引只建一次，不需要更新，强调索引数据的存储效率和查询效率，不强调索引更新的效率。动态索引结构强调数裾在动态史新过程中保证较高的查询效率和索引空间存储效率，往往以牺牲索引史新效率为代价，这种牺牲是宥限度的。索引结构还分为内存索引和外存索引，外存索引需要考虑磁盘页而访问的效率瓶颈问题。这里主要研究面向海a空问数据的、2D空问对象的外存索引结构。7.1空间索引分类非空间数据库中存储的数据力结构化数据，通常以主关键字建立索引文件，以非主属性建立倒排文件，索引项按自然数序列或字符顺序排列。空间数

6、据库存储的数据为结构复杂、不能完全结构化的空间数据，为了支持基于位置的各类査洵和分析，需要以表示空间对象几何形状的坐标数据为索引字段来建立空间索引。非空间数据库的索引结构不能满足空间数裾库的索引需求，必须研允和设计专用的空间索引结构和基于索引的空间访问方法（SAMSpatialAccessMethod)7.1.1非空间索引与SAM非空间索引结构一般为B树和hash文件结构，这种索引结构可以准确的定位和查找所需数据，复杂度为对数函数。一、索引的假设和要求（一）B树和hash文件结构遵从的假设1、被索引的数据集所占

7、空间远远大于内存空间；2、磁盘访问比内存访问慢得多；3、对象按物理贞分组，贞是内存和外存交换数据的单位（大小为1K到4K），读/写一页力一次I/O操作。4、访问一个具体对象时，该对象所在页可能在内存中，或不在内存中需要调入内存。非空间数据库的索引操作屮，CPU时问与I/O操作时间相比可忽略不计，访问方法的效率用I/O数衡量。空间索引的操作中，有些情况下需考虑CPU时间，但不考虑页的缓存，使用一页时才调入内存。（二）SAM成满足的要求空间索引是依据空间对象的空间位置、几何形状及空间分布特征，按一定顺序排列的一种数

8、据结构。空间访问方法SAM的设计基于B树和hash表相同的假设，但B树和hash表均不适合于空间索引。SAM应满足下列要求：1、时问复杂度：点选择和区域查询应具有线性复杂度。SAM访问一个数据集合的子集所用的吋间，应小于以集合元素数量的线性函数为«杂度的序列查找兑法。2、空问复杂度：如果被索引的集合占据n页，索引的大小应该是n级的。3、空问索引结构必须考虑动态性：适合于空问索引项的增加