第十章基于空间目标排序的索引方法

收稿日期:2010-01-25;修回日期:2010-04-10基金项目:湖北省自然科技基金(2007ABA025)作者简介:熊才权(1966-),男,湖北鄂州人,博士,教授,研究领域为人工智能、数据挖掘、空间数据库。

空间索引技术研究熊才权1,马乐乐1,孙贤斌2(1.湖北工业大学计算机学院,湖北武汉430068;2.湖北工业大学土木工程与建筑学院,湖北武汉430068)摘 要:空间索引可以提高空间数据库的操作效率,目前人们的研究工作更多地集中在空间数据的多维索引的研究上。

文中全面地总结了当前空间数据库领域中空间索引以及时空索引的研究进展,描述了R 树系列索引的构建思想,节点插入与分裂操作的不同。

通过实验深入分析了R 树以及R 树变体的磁盘访问率,插入,删除,更新的CPU 时间,验证了在数据激增的情况下,R 树系列索引的复杂性带来的重叠问题会指数递增。

由于R 树当前应用的深度和广度,研究基于R 树的高效时空高维索引技术是解决索引应用问题一个有效方法。

提出了索引性能改进的方向在于多种索引技术的结合,尤其是树形结构索引和网状结构索引的结合。

关键词:空间数据;R-tree;空间索引;高维索引;时空索引中图分类号:T P311 文献标识码:A 文章编号:1673-629X(2010)10-0219-05Research on the Technology of Spatial IndexXIONG Ca-i quan 1,MA Le -le 1,SU N Xian -bin 2(1.School of Computer ,Hubei U niversity of T echnolog y,W uhan 430068,China;2.School of Civil Engineering and Architecture,Hubei U niversity of T echnolog y,W uhan 430068,China)Abstract:Spatial index can improve operational efficiency of the spatial database.Research is now more focused on th e multi-dimensi onal spatial data research on the index.In thi s paper,a comprehensive summary of the current field of spati al database research space indexed and spatiotemporal i ndex by a number of experimental pop-depth analysis of the index structure,describes the construction thi n ki ng,node inserti on and split operation of the R tree index series,through experiments i n-depth analysis the CPU time w hich the R tree and R tree variants .s disk access,insert,delete,update.Verify the case of surge in the data,R tree fami ly index of overlap caused by the complexity of the problem exponenti ally.As the R tree depth and breadth of the current applicati on,it is an effective w ay to solve applica -tion problems of index that research on the efficient tree-based on R tree high di m ensional space-time techniques.Fi nally proposed to improve the performance of the directi on of the index is a combination of a variety of indexing techniques,i n particular,the index tree structure netw ork structure and the combination of the index.Key words:spatial data;R-tree;spatial index;high dimensional index;spatiotemporal index0 引 言空间数据库的概念是随着地理信息系统的发展而逐渐引起人们的重视的。

一、判断题（第一章绪论）1.数据元素是数据的最小单元。

答案：错误2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。

答案：错误3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。

答案：正确4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。

答案：错误5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间答案：正确（第二章线性表）6.取顺序存储线性表的第i个元素的时间同i的大小有关。

答案：错误7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

答案：正确8.线性链表的每一个节点都恰好包含一个指针域。

答案：错误9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。

答案：正确10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

答案：错误（第三章栈）11.栈是一种对进栈和出栈作了限制的线性表。

答案：错误12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。

答案：错误13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。

答案：正确14.空栈就是所有元素都为0上的栈。

答案：错误15.将十进制数转换为二进制数是栈的典型应用之一。

答案：正确（第四章队列）16.队列式限制在两端进行操作的线性表。

答案：正确17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。

答案：错误18.在循环链列队中无溢出现像。

答案：错误19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。

答案：正确20.顺序队列和循环队列关于队满和队空的判断条件是一样的。

答案：错误（第五章串）21.串是n个字母的有限序列。

答案：错误22.串的堆分配存储是一种动态存储结构。

答案：正确23.串的长度是指串中不同字符的个数。

3D GIS空间索引技术3DGIS是新一代GIS技术的重要分支，是进行全方位、多层次、多要素时空分析的基础，开发结构简单、功能完善的真3DGIS软件是当前GIS研究人员的重要目标。

3DGIS需要管理大量的三维空间对象，且常常需要根据空间位置对这些对象进行查询、检索和显示操作。

为了处理这类空间操作，传统的关系数据库搜索方法需要花费大量的磁盘访问时间和空间运算时间。

为了提高检索效率，传统的关系数据库一般都建立一系列的索引机制，如B+树等。

目前常用的索引机制多是一维索引，无法有效处理3DGIS空间数据库中的三维空间地理实体。

因此，必须为3DGIS空间数据库建立专门的索引机制——空间索引。

空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按照一定规律排列的数据结构，它介于空间操作算法和空间对象之间，筛选、排除与特定的空间操作无关的空间对象。

空间索引机制是快速、高效地查询、检索和显示地理空间数据的基础，其性能优劣直接影响GIS空间数据库的性能，关系到3DGIS软件系统的整体运行状况。

一、三维空间索引简介3DGIS是2DGIS在三维空间内的延展，是布满整个三维空间内的GIS，它与2DGIS的差异主要体现在空间位置的确定、空间拓扑关系的描述与空间分析的延展方向上。

3DGIS将三维空间坐标（x，y，z）作为独立的参数来构建空间实体对象模型，能够实现空间实体的真三维可视化，以立体造型来展现空间地理现象，它不仅能够表达空间实体之间的平面关系，还能够表达其垂向关系，在此基础上进行复杂的三维空间分析与操作。

在GIS由二维扩充到三维后，其处理的空间对象也由二维空间中的“点、线、面”扩充到三维空间中的“点、线、面、体”。

2DGIS对平面空间的“有限-互斥-完整”剖分是基于面的划分，而3DGIS对三维空间的“有限-互斥-完整”剖分则是基于体的划分。

在3DGIS 空间数据库中，空间实体的表达形式复杂，各种空间操作不仅计算量大，而且多具有面向邻域的特点。

PPT思考题：绪论：地理信息是描述地表形态及其所附的自然和人文地物特征和属性的总称。

地理空间是一个相对空间，是一个空间实体组合排列集，强调宏观的空间分布和空间实体间的相关关系。

空间数据是指带有空间坐标的数据（非结构化特征）。

1、什么是空间数据库？是以特定的信息结构和数据模型表达、存储和管理从地理空间中获取的某类空间信息，以满足不同用户对空间信息需求的数据库。

2、空间数据库系统包括哪几部分？（1）矢量地形图数据库（2）数字高程模型库（3）影像数据库（4）数字栅格地形图（5）专题数据（6）电子地图（7）元数据3、空间数据库主要作用有哪些？（1）海量数据的管理能力（2）空间分析功能（3）设计方式灵活，满足用户要求（4）支持网络功能4、当前空间数据库存在的主要问题是什么？空间数据的获取与处理空间数据组织空间数据库系统空间数据共享研究5、影响空间数据库发展的关键因素是哪几个?空间数据库的计算平台；空间数据模型；空间数据库的组织管理模式。

第二章空间现象计算机表达1、空间实体：具有确定的位置和形态特征并具有地理意义的地理空间的物体2、空间索引相关概念及其包括哪些索引方式？空间索引：依据空间对象所在位置及分布特征，按一定顺序编排的一种数据结构，且该数据结构包含有对象标识和定位这些对象的内容的信息空间数据索引：是指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针空间检索: 给定查询条件，利用空间索引从数据库中找出符合条件的空间数据的一种操作索引方式：BSP树、K－D－B树、R树、R+树和CELL树3、数据挖掘，空间数据挖掘有哪些方法？数据挖掘：一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程方法：分类、回归分析、聚类、关联规则、特征、变化和偏差分析、Web页挖掘等4、地理系统：是指各自然地理要素通过能量流、物质流和信息流的作用结合而成的，具有一定结构和功能的整体，即一个动态的多等级开放系统5、栅格结构与矢量结构的比较第三章空间数据的物理组织文件管理：文件系统把有关数据组织成为文件并予以命名分页技术：即把内、外存空间按同样大小分成若干页面系统缓冲区：是主存中特别指定的一块存储空间，以存放从外存读入内存的数据或从内存写进外存的数据缓冲区管理：就是将缓冲区分成若干块，系统用一个程序分配这些缓冲块，并采用分配算法使缓冲区的利用为最佳文件组织：就是按一定的逻辑结构把有关联的数据记录组织成为文件（称为逻辑文件），用体现这种逻辑结构的物理存储形式把文件中的数据存放到某种存储设备上，使之构成物理文件的机构动态存储管理：研究数据结构的空间分配、回收的方法，以满足某种结构对存储的不同要求流水文件：是一种最简单的文件组织方法，即按照数据到达文件的时间顺序依次连续地存储数据，对数据不分析、不规范，记录的类型既可相同，也可不同索引文件：将每页的最后一个单词与页号列表，那么查单词可先查表（称为索引表），等确定页面号后，再细查该页面。

R树空间索引
R树是一种多级空间索引结构，用于快速查找和检索具有空间范围的多维数据。

它基于以下原理：
1. 覆盖矩形 (MBR)
每个数据项（称为节点）用一个最小包围矩形（MBR）表示。

MBR包含该数据项的所有空间范围。

2. 分组和层级
R树是一个分层结构。

它将数据节点分组到叶节点中，然后将叶节点分组到内部节点中，依次类推。

3. 访问路径
要查找一个对象，会从根节点开始，并递归地向下遍历树。

在每个节点中，会选择最合适的子节点（具有最小的MBR覆盖目标范围）继续搜索，直到到达叶节点。

4. 分割算法
当一个节点包含过多数据项时，它需要被分割成更小的子节点。

R树使用以下分割算法之一：
•线性分割：将节点中的MBR按某一维度排序，并将其分割成两个近似相等的子节点。

•平方分割：将节点中的MBR按面积排序，并将其分割成两个面积近似相等的子节点。

R树的优点
•快速查找：通过逐步缩小搜索空间，R树可以快速查找具有空间范围的数据项。

•动态更新：R树可以有效地处理数据项的插入、删除和更新。

•高维数据：R树可以用于高维数据，并且在实际应用中表现良好。

R树的缺点
•内存开销：R树需要存储大量MBR，这可能会导致较高的内存开销。

•可能出现重叠：R树中的MBR可能会重叠，这可能会影响查找的效率。

空间索引方法
空间索引方法是一种用于管理和查询空间数据的技术。

它在许多领域都有广泛的应用，如地理信息系统、地震学、生物学等。

空间索引方法的主要目标是提高查询效率，减少查询时间和资源消耗。

在空间索引方法中，首先需要定义空间对象的属性和关系。

然后，根据这些属性和关系，构建空间索引结构，以便快速定位和检索数据。

常见的空间索引方法包括：网格索引、四叉树、R树、k-d树、多级
索引等。

网格索引是一种最简单的空间索引方法，将空间分成规则的网格，每个网格对应一个索引节点。

四叉树是一种二叉树结构，每个节点都有四个子节点，将空间不断分割成四个象限。

R树是一种多叉树结构，每个节点都有多个子节点，能够更好地处理空间中的重叠区域。

k-d
树是一种二叉树结构，每个节点都表示一个k维空间中的点，将空间不断分割成两部分。

多级索引是一种混合索引方法，结合了多个不同的索引结构，以提高查询效率。

除了以上几种常见的空间索引方法，还有很多其他的方法，如基于哈希的索引、基于图的索引、基于邻域图的索引等。

这些方法都有其各自的优点和适用范围，需要根据具体的应用场景选择合适的方法。

- 1 -。

空间索引与空间填充曲线
空间索引和空间填充曲线都是地理信息系统中常见的概念，它们在地理数据处理和空间数据组织中起着重要的作用。

首先，让我们来谈谈空间索引。

空间索引是一种用于提高地理数据检索效率的数据结构。

它可以帮助我们快速查找空间数据中的对象，比如点、线、面等。

常见的空间索引包括R树、Quadtree、KD树等。

这些空间索引结构可以将地理数据分层组织，通过节点之间的关系来快速定位和检索数据。

空间索引的设计和选择对于地理信息系统的性能和效率至关重要，因为它们可以显著减少数据访问的次数，从而提高查询的速度和效率。

接下来，我们来探讨一下空间填充曲线。

空间填充曲线是一种将多维空间映射到一维空间的技术。

它可以将相邻的多维空间对象映射到相邻的一维空间位置，从而实现对多维空间的快速检索。

常见的空间填充曲线包括希尔伯特曲线、莫尔斯曲线等。

通过空间填充曲线，我们可以将地理数据转换成一维的线性数据，然后利用传统的一维数据结构进行检索和分析。

这种技术在地理信息系统中被广泛应用，特别是在空间数据压缩、相似性搜索和空间数据聚类等方面发挥着重要作用。

总的来说，空间索引和空间填充曲线都是地理信息系统中重要的概念和技术。

它们通过不同的方式来提高地理数据的检索效率和分析能力，为地理信息系统的应用提供了重要的支持和保障。

在实际应用中，我们需要根据具体的需求和数据特点来选择合适的空间索引和空间填充曲线，以达到最佳的数据组织和检索效果。

格雷空间填充曲线
答：格雷空间填充曲线是一种基于格雷码的空间索引方法。

其基本思想是将空间目标按某种策略细分为许多均等的网格，并给每一网格分配一个编号，然后用这些编号为空间目标获得一具有代表意义的数字。

这样，多维空间目标就可以背影射成一维的目标，从而也就可以使用现有的数据库管理系统中比较成熟的一维索引技术来提高对空间数据的快速查找和存取。

格雷空间填充曲线的实现过程如下：
1. 将X，Y轴转换成二进制值，并获得其对应的格雷编码。

2. 将X与Y的格雷编码两两交叉，形成新的二进制串。

3. 将该二进制字符串转换成其对应的格雷编码。

这样就形成了对应的格雷空间填充曲线。

通过这种方法，高维空间中的数据可以被映射到一维空间，从而降低了空间维度。

这有助于使用经典线性索引结构存储数据，并且能够较好地保持多维空间目标间的临近关系，提供较好的空间查询性能。