时间：2022-10-31 10:30:01 | 来源：信息时代
时间：2022-10-31 10:30:01 来源：信息时代
空间索引管理 : 在数据库中高效处理空间查询而设计的索引结构,它的目标是要便于空间选取和空间连接查询。在响应一条查询时,空间索引方法只需查找该空间中所有对象的一个关联子集,并将其返回至查询结果集中。
1.空间索引实现方法
空间索引的基本思想是按照一个或多个空间关键码来管理空间对象。空间关键码是比空间对象本身更简单的几何对象,对于矢量结构而言通常采用外接矩形,对于栅格结构采用规则格网单元。空间索引使用一种用于查询过程的过滤和精练策略: 首先在空间关键码的基础上,执行一个过滤步骤,返回一个候选集,作为完全满足某个谓词的所有对象的超集;其次,在精选步骤中,对于每一个候选对象(或者在空间连接中的一对候选对象)用精确的几何信息进行检查。由于使用了外接矩形,大多数空间索引结构都被设计成可以存储一组点(点值)或一组矩形(线或者区域值)。
空间索引结构用一组存储桶(bucket)(通常对应二级存储器的页面)来组织对象。每个存储桶有一个关联的桶区域,即包含了存储在桶中全部对象的一部分空间。桶区域通常是矩形的。对于点数据结构,这些区域通常是不相交的,它们分割空间使每个点正好属于一个存储桶。对于一些矩形数据结构,桶区域可能是交叠的。
提供空间索引的基本方法有两种:
(1)在系统中加入为空间属性专门扩展的索引数据结构,提供如同B-树之于线性属性的功能。
(2)使用空间填充曲线(如Z-序、Hilbert曲线)将空间映射到一维,以便存储在标准的一维索引中,例如B树。
除了空间选取,空间索引还支持其他的操作,例如,空间连接、查找最符合待查询值的对象等。
2. 空间索引结构
常用的空间索引结构有聚簇索引(z-序、Hilbert曲线)、格网文件、R-树等。
(1)空间聚簇索引: 在二级存储器中,使空间上邻近的和查询上有关联性的对象在物理上存储在一起,称为空间聚簇索引。在空间数据库中采用聚簇索引结构来存储空间数据能够减少I/O代价。聚簇的目的就是降低一般大查询的寻道和等待的响应时间。空间数据库中有三种用于提供有效查询处理的聚簇存储结构: ①内部聚簇: 一个对象的全部数据都存放在同一个磁盘页面中,这里假设它比页面的空闲空间小; 否则,这个对象就要存储在多个物理上连续的页面中。这种情况下,对象占用的页面至多比存储该对象所需最少页面多一个页面。②本地聚簇: 一些空间对象(或者近似值)被分组到同一页面,这种分组可以依照数据空间中对象的位置(或近似)来施行。③全局聚簇: 与本地聚簇相反,一组空间邻接的对象并不存储在一个而是多个物理上邻接的页面中,这些页面可以由单条读命令访问。
由于空间数据所处的多维空间中没有天然的顺序,而存储磁盘是逻辑一维的设备,因此,空间聚集索引技术需要一个从高维空间向一维空间的映射。该映射是距离不变的,使空间上邻近的元素映射在直线上接近的点,而且一一对应,即空间上的任意两个点不会映射到直线上同一个点。
空间填充(space-filling)曲线的方法是利用一个线性顺序来填充空间,可以获得从一端到另一端的曲线。主要包括Z序(Z-order)、格雷码(Gray code)和Hilbert曲线。
(2)格网文件: 格网文件是采用多属性索引技术来分割n维空间的索引方法。从局部上来看,它采用了固定格网方法。固定格网是访问多维点的最简单的结构(例如经纬网)。固定格网方法将n维空间划分成同等大小的存储桶,其数据结构是一个n维数组。位于一个单元中的点可以存储在一个动态结构中(例如链表)来处理溢出。这种结构对于静态一致分布的数据(例如卫星影像)很有用。然而,固定格网结构是定死的,它的目录稀疏而巨大。
格网文件达到了更好的灵活性和性能。它对于精确匹配和部分匹配提取都有较好的I/O性能。使用格网文件的目标就是为了实现二次磁盘访问原则: 一次是访问获得目录项,另一次是得到实际存储桶以获取实际记录。格网文件有两部分: 第一部分包括一个n维格网目录,目录中每一项指向一个数据存储桶;第二部分是线性增长的一维数组结构,这个数组用来标识格网目录的索引,该索引引用了包含对象(记录)的块或存储桶。
格网文件的查询时间很短,对于精确匹配查询,只作一次到目录的磁盘访问和一次数据访问。然而,格网文件本质上会造成目录非常松散,导致主存缓冲区和二级存储器的浪费。例如,超立方体可能只有非常少或没有记录,邻近目录项可能指向同一个数据块。这就意味着,对于局部匹配和范围查找,需要扫描很多只有少量数据块的目录项。
(3) R-树: R-树是用于索引空间对象的高度平衡树,是B-树在k维上的自然扩展。R-树中用对象的最小外接矩形来表示空间对象。由于R-树采用的是数据驱动的方法,因此不会因为空间对象的分布稀疏而造成存储浪费。
R-树的结构与特性:①每个叶结点包含m至M条索引记录(其中m≤M/2),除非它是根结点。②一个叶结点上的每条索引记录是(I,元组标识符),I是最小外接矩形,在空间上包含了所指元组表达的k维数据对象。③每个非叶结点都有m至M个子结点,除非它是根结点。④对于非叶结点中的每个条目(I,子结点指针),I是空间包含其子结点中矩形的最小外接矩形。⑤根结点至少有两个子结点,除非它是叶结点。⑥所有叶出现在同一层。⑦所有最小外接矩形的边与一个全局坐标系的轴平行。
R-树的存储结构: ①R-树的每个结点对应一个磁盘页面。一个叶结点包括一组项,格式为(I,元组标识符),其中I为最小外接矩形,元组标识符是数据库中对应最小外接矩形的存储对象的元组唯一标识。用I=(I0,…,Ik-1)表示I,其中Ii在沿方向i的一个闭合区间[a,b]上。非叶结点由多个格式为(I,子结点指针)的项组成,其中I是子结点指针指向的更低层结点项中所有矩形的最小外接矩形。树中每个结点最多有M个条目,最少有m个(m≤M/2),除非它是根。根结点至少有两个子结点,除非它是叶。②由于R-树是一棵平衡树,在对应插入对象的叶结点已满的情况下,插入操作可能会导致结点向根部分裂。叶面分裂算法非常复杂。不过,R-树已经在许多商用数据库系统中实现了,它们支持通用的存取方法和合理大小(1024字节)的磁盘页面。R-树的最大层数是logmN-1,其中N是树中条目的总数。在最坏情况下,除根之外,结点空间的利用率是m/M。如果m大于3或4,树将水平扩展,这样,几乎所有的空间都用于存储索引记录的叶结点。m值增大就意味着R-树的深度相对变浅。R-树是一个动态结构,还允许存储不同类型的对象。
基于R-树的查询与性能: 点和范围查询在R-树中可以用自顶向下递归的方法处理。查询点(或区域)首先与根结点中每个项(I,子结点指针)进行比较。如果查询点在I中(或查询区域与其交叠),则查找算法就递归地应用在子结点指针所指向的R-树结点。该过程直至R-树的叶结点为止。使用叶结点中选出的项来得到与选中空间主码关联的记录。
R-树的查询性能取决于两个因素:覆盖和交叠。树中一层的覆盖是指这一层所有结点的最小外接矩形所覆盖的全部区域。覆盖是对静态空间的间接衡量,或者是树覆盖的空白区。树中一层的交叠是指被不止一个该层结点关联的多边形所覆盖的全部区域。交叠使得查找一个对象需要访问树的多个结点。R-树的这个问题意味着,即使已经尽量减少了交叠,查询操作的最差性能仍然是无法估计的。若要得到一个高效的R-树,覆盖和交叠都应该最小,而且交叠的最小化要比覆盖更具有决定性。由此导致了其他基于R-树的变种和备选结构。例如,packed R-树、R*-树和R+-树。
R+-树的结构: 在R+-树中,空间对象的最小外接矩形可能被树中非叶结点的矩形分割。R+-树有如下特点:①对于中间结点的每个项(I,child-pointer),由child-pointer指向结点为根的子树包括一个矩形R,当且仅当R被I覆盖。唯一的例外是当I是一个叶结点的矩形。在这种情况下,R与I只交叠。②对中间结点的任何两个项(I1,child-pointer1)和(I2,child-pointer2),I1与I2之间的交叠是零。③根至少有两个子结点,除非它是叶结点。④所有的叶都在同一层。⑤中间结点的所有矩形都是不相交的,因而中间结点项之间零交叠。如果一个对象的最小外接矩形被两个或多个R+树高层结点的矩形分割,与这些非叶结点中矩形相对应的每个项都有一个派生的叶结点指向这个对象。这样,树的高度增加(虽然只是轻微的),但查询操作的性能会有很大提高。
对于高度动态的数据,R+-树比packed R-树更好,因为它确保了持续的高效。同R-树相反,由于R+-树的第一个特点,它可能会需要向下分裂。因此对分裂结点的选择很重要。
在线咨询
