2022年2022年空间数据库的索引技术 .pdf

第22卷 第3期2005年6月 黑 龙 江 大 学 自 然 科 学 学 报JOURNAL OF NATURALSCIENCE OF HE ILONGJ IANG UN I V ERSITYVol122No13June,2005空间数据库的索引技术郭龙江1,2,李建中1,2(1.哈尔滨工业大学计算机科学与技术学院,黑龙江 哈尔滨150001;2.黑龙江大学计算机科学与技术学院,黑龙江 哈尔滨150080)摘 要:由于空间数据库中的数据量很大,因此空间数据库查询的开销一般要比关系数据库大,特别是查询语句的条件谓词中包含一些对空间数据操作的函数,计算这些函数的开销远比数值或字符串的比较要大。如果用顺序扫描的方法查询,则效率非常低。因此,为了提高查询效率,采用空间索引是十分必要的。目前人们的研究工作更多地集中在空间数据的多维索引的研究上。全面地总结了当前空间数据库领域中空间索引的研究进展,然后介绍了目前空间数据库中广为采用且比较新的4种索引方法:(1)R树(2)K-D 树(3)Quad树(4)GiST。最后指出在空间数据库中的高维索引的研究是目前前沿研究的热点。关键词:空间数据;空间数据库;空间索引;高维索引中图分类号:TU313文献标识码:A文章编号:1001-7011(2005)03-0288-06收稿日期:2004-04-03作者简介:郭龙江(1973-),男,博士研究生,讲师,主要研究方向:数据库,数据流上的数据挖掘技术,传感器网络,E2mail:通讯作者:李建中(1950-),男,教授,博士生导师,国家科学技术进步奖二等奖获得者,E2mail:1 引 言近几年,人们对地理资源、地球环境以及地理信息进行研究时产生了大量的空间数据。与此同时,遥感、卫星图像处理、人体医疗成像等应用也提供了大量的空间数据信息。人们需要存储和管理大量的空间数据,同时还要在大量的空间数据上进行快速的查询和计算。目前的商用数据库管理系统(DBMS)处理空间数据有一定的困难,因此人们提出了空间数据库的概念。由于空间数据库中的数据量很大,因此空间数据库查询的开销一般要比关系数据库大,特别是查询语句的条件谓词中包含一些对空间数据操作的函数,计算这些函数的开销远比数值或字符串的比较要大。如果用顺序扫描的方法查询,则效率非常低。因此,为了提高查询效率,采用空间索引是十分必要的。目前,人们的研究工作更多地集中在空间数据的索引研究上。当前,人们已经提出了很多种多维索引技术。这些多维索引技术包括Bang 7文件,、网格文件 15、hB树 14、KDB 树 16、Para mid树 2、四叉树 17、R树 10、R3树 1、R+树、TV树和 VA 文件 19,这些索引主要是用来对点的集合进行索引。能够同时处理区域数据和点数据的索引结构包括区域四叉树、R树和SK D 树。文献 9 讨论了针对由线性约束定义的区域如何用R树进行索引。这些技术的一些变形和其它几种不同的技术也被提出来了,Sa met的文章 18 处理了它们中间的很多问题。文献 8 是到目前为止最新的综述。文献 6 提出了线性化多维数据的H ilbert曲线的使用。文献 4讨论了空间连接的问题。为了能够适应更复杂的数据类型的索引,人们还提出了通用搜索树GiST 11。用户可以在自定义空间数据类型的基础上,自行定义树的插入、删除、修改、搜索操作,更有效地实现空间数据类型的查询。通用搜索树GiST,它可以被实例化成各种树的索引。文献 13 讨论了GiST的并发控制和恢复问题。文献 21 讨论了GiST的并行化问题。文献 12讨论了索引机制的复杂性,特别是针对区域查询。文献 3讨论了高维索引这个问题。文献 5 是一个综述,总结并讨论了如何在基于内容的多媒体数据库中进行检索。最新的研究趋势是时空数据库的应用,文献 20中讨论了跟踪移动对象等问题。到目前为止还没有被一致认为是“最好”的空间索引结构。但是,应用最广泛的是R树。R树有许多变?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -形,包括 Cell树、H ilbert R树、PackedR树、R3树、R+树、T V 树和 X树。已经可以在商用的DBMS中看到R树索引。这是由于R树相对简单,能同时处理点和区域数据,而且它的性能至少比那些更复杂的索引结构不差。本文的内容安排如下:在第 2节中,讨论了R-树的存储结构以及如何在R-树上进行增、删、改操作以及搜索操作。第 3节给出了K-D 树的存储结构。第 4节给出了Quad树的存储结构。第 5节介绍了GiST树的存储结构以及函数操作接口。第 6节讨论了空间数据库的高维索引问题。2R-树R树是处理空间数据的B+树的改进,它像 B+树一样,是一个高度平衡的数据结构。R树的搜索码是区间的集合,一个区间是一维。可以把搜索码看成是一个被这些区间所包围的方框,方框的每一条边都和坐标轴平行。R树中搜索码的值将被称为边界框。叶子节点中包含数据项。一个数据项是由对组成的,这里rid标识一个对象,方框是包含这个对象的最小方框。作为特殊情况,如果数据对象是一个点而不是区域,那么这个方框就是一个点。非叶子节点包含的索引项的形式为。在非叶子节点N 上的方框是包含所有以节点 N 为子树根的所有数据对象的区域。下图描述了数据对象和边界框在空间是如何分布的以及数据对象的分布所对应的R树实例。在实例树中有19个区域。区域R8R19表示数据对象,同时在叶子级别上表现为数据项。区域 R1R7表示树的内部节点的边界框。例如区域R1是包含左子树空间的边界框,它包括数据对象R8、R9、R10、R11和 R12。一个给定节点的两个孩子的边界框可以重叠,例如,根节点的孩子边界框R1和 R2是重叠的。这意味着一个满足所有边界框约束的给定数据对象可以包含在多个叶子节点中。但是,每个数据对象都精确地存储在一个叶子节点中,即使它的边界框落在多个高层节点对应的区域内。例如,考虑 R8表示的数据对象。它同时包含在R3和 R4中,可以被放置在第一个或者第二个叶子节点中(在树中从左到右)。这里选择将它插入到最左边的叶子节点中而没有插人到树中其他任何地方。211R-树的搜索操作为了搜索一个点,需要计算对应该点的边界框B,然后从树根开始查找。首先测试树根的每个孩子的边界框以确定它是否与查询框B重合,如果重合就搜索以这个孩子为根的子树。如果树根的多个孩子的边界框都与 B重叠,那么就必须搜索所有相应的子树。这是与 B+树的一个重要差别:即使一个点也可能导致搜索沿着树的几条路径进行。当到达叶子节点时,检查叶子是否包含需要的点。当查询点所在的区域不被任何一个与叶子节点相对应的框覆盖时,就可能不会访问到一个叶子节点。如果搜索没有访问到任何叶子节点,那么查询点就不在索引的数据集中。区域对象的搜索和区域查询的处理是类似的,都是首先计算需要的区域边界框,然后像搜索一个对象那样进行区域查询,当到达叶子节点后,检索属于该叶子的所有区域对象,并测试以确定它们是否与给定的区?982?第 3期郭龙江等:空间数据库的索引技术?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -域重叠(或者被包含,这取决于查询)。需要注意的是即使对象的边界框与查询区域重叠,对象本身也可能不重叠!例如,假设查询区域是表示对象R9的边界框,希望找出查询区域覆盖的所有对象。首先,从树根开始,发现查询框与R1重叠而不与R2重叠。这样,就搜索左子树,而不搜索右子树。接着发现查询框与R3重叠而不与R4重叠,因此继续搜索最左边的叶子,找到对象R9。为了搜索一个给定点的最近的邻居,可以像搜索点本身一样进行处理。先检索作为搜索的一部分的叶子节点中的所有点,然后返回与查询点最近的点。如果没有访问到任何叶子节点,就以查询点为质心的一个小边界框代替查询点,重复搜索。如果还是不能访问到任何叶子节点,就增大框的范围,然后再次进行搜索,继续这个过程直到找到一个叶子节点为止。于是,在搜索的迭代中考虑了从叶子节点中检索到的所有点,然后返回与被查询点最近的点。212R-树的插入和删除操作为了插入rid为 r的数据对象,需要计算对象的边界框B,然后将对插入到树中。从根节点开始遍历从根节点到叶节点的一条单独路径(与搜索相比,搜索可能要遍历几条这样的路径)。在每一级选择这样的子节点:它的边界框只需最小的扩大(按照面积的增长进行度量)就可以覆盖边界框B。如果几个子节点都可以覆盖B的边界框(或者是为了覆盖B的边界框需要相同的增长),那么从这些子节点中选择具有最小边界框的节点。在叶子级插入对象,而且如果有必要还需要扩大叶子节点的边界框来覆盖边界框B。如果需要扩大叶子节点的边界框,那么叶子节点的祖先的边界框就必须扩大,为什么呢?因为在插入完成以后,每个节点的边界框都必须覆盖所有后代的边界框。如果叶子节点没有空间以插入新的对象,就必须把节点进行分裂,然后把数据项重新分布到老的叶子节点和新的节点。同时必须调整老叶子节点的边界框,将新叶子节点的边界框插入到它的父亲中。当然,所有这些改变能够沿着树向上进行传播。为了从R树中删除一个数据对象,先执行搜索算法,并且可能还要检查多个叶子。如果对象在树中,就去掉它。原则上,尽量缩小包含对象的叶子的边界框以及所有祖先节点的边界框。在实际中,通常只是简单地将对象移走来实现删除操作。3K-D树为了理解如何索引二维或高维的空间数据,首先考虑对一维数据中的点进行索引。树结构(如二叉树和 B树)的操作是连续的把大的空间划分成一些较小的空间。例如:二叉树的每个内结点把一个一维区间划分成两个子区间。左区间中的点存储到左子树,右区间中的点存储到右子树。平衡二叉树中,每个划分的区间应该近似包含子树中的点的一半。类似的,二叉树的每一层把一个一维区间划分成多个部分。根据上述直觉,能够为二维或高维空间创建树结构。K-D 树是用于索引多维数据的早期数据结构之一。K-D树的每层都把空间划分为两个部分。划分沿着树的顶层结点中的一维进行,然后是下一层结点中的其它维,等等如此划分下去。划分尽量使子树中的结点有一半属于一个划分,另一半属于另一个划分。当结点中包含的点数少于叶子结点中包含的最大点数时停止划分。图 3显示了用K-D 树表示一个二维空间中的点集。每条线对应树中的一个结点,叶子结点中包含的最大点数设置为1。线号表示对应结点出现在树中的层数。为减少树的高度,把 K-D树扩展为K-D-B树,就象把二叉树扩展为B树一样。K-D-B 树比K-D 树更适合索引二级存储器中的数据。4Quad树二维数据的另一种表示方法是使用Quad树。图 4显示了Quad树对空间的划分。Quad树中的每个结点对应空间中的一个矩形区域。顶层结点对应整个目标空间。树中的每个非叶子结点把该结点对应的区域划分为四个大小相等的象限,每个象限有一个孩子结点与之对应。叶子结点包含点的数目介于零和某个定值之间。相应的,如果一个区域对应的结点包含的点数超过了这个最大值,则需要为这个结点创建孩子结点。在图4的例子中,叶子结点中的最大点数为1。?092?黑 龙 江 大 学 自 然 科 学 学 报 第 22卷?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -可以使用区域Quad树(region quadtrees)来存储数组信息。如果区域Quad树中的结点覆盖的区域中所有数组元素的值都相同,则该结点是叶子结点。否则,该结点是内部结点,被进一步划分为四个等大小的子结点。区域 Quad树中的每个结点对应一个子数组的所有值。对应叶子结点的子数组,或者包含一维数组元素,或者包含多维数组元素,所有元素的值都是相同的。5GiSTB+树和R树在许多方面是类似的:它们都是高度平衡的,搜索都是从根节点开始,然后向叶子节点处理,每个节点覆盖底层数据空间的一部分,同时节点的子节点覆盖与节点相关联的区域的子区域。当然两者还有很重要的差别,例如,在B+树的表示中,空间是线性化的,但是在R树中不是这样。它们的共同特征使它们在插入、删除、搜索甚至并发控制上有很大的相似之处。美国威斯康星大学JosephM.Hellerstein 于1995年在 VLDB 会议上首先提出GiST(GeneralizedSearch Trees),称之为通用搜索树。GiST抽象出树索引结构的基本特征,并为插入、删除和搜索提供“模板”算法。GiST的核心思想是一个对象关系DBMS可以支持多个模板算法,因此使得高级数据库用户实现特定的索引结构更容易(例如 R树及其变形)而不需对任何系统代码做改动。实现扩充比从头实现新的索引算法花费要少很多。许多特殊的搜索树都可以通过GiST实现。可以说,GiST统一了所有不同的树结构,它是特殊搜索树的模板。GiST向用户提供一组函数接口,这些接口需要用户来实现,然后再注册到数据库系统中。这组函数既反映了用户自定义类型的结构和特点,也反映了对已用户自定义类型为索引关键字的GiST树的基本操作。GiST是一棵平衡树,它提供了一些模板算法用于周游、删除、修改、分裂、合并。与其它搜索树类似,叶结点存储(key,ptr)对,key是索引关键字,ptr是指针,指向包含记录的数据块在磁盘上的地址。内部结点包含(p,ptr)对,p是一个逻辑谓词,它描述用户要查找的数据是否在ptr所指向的子树中。GiST的所有叶结点用链表连接起来。GiST结构见图5。它有如下特性:a)根结点至少有2个子女。b)每个内部结点包含的子女数记为N,k M N M。其中k称为最小填充因子,2/M k1/2。实际上,每个GiST结点包含N 个(p,ptr)对,p是一个抽象谓词,ptr是一个指针,它指向一棵子树,子树的叶结点中包含符合谓词p的记录。称(p,ptr)是一个入口(Entry),简记为E。规定,在GiST中所有结点大小相同,最多包含M个入口。如果结点中含有少于M个入口,则其余的位置空缺,以便其它的入口插入到GiST中。c)对于叶结点上的每一个入口E=(key,ptr),key?192?第 3期郭龙江等:空间数据库的索引技术?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -中存放记录的关键字,ptr指向真实的记录。d)所有的叶结点都处在同一层。叶结点所处的这一层规定为0层,叶结点的父亲所处的一层是1层,。以此律推,子女所处的层数等于父亲所处层数减1。GiST本身提供了一系列操作算法:插入算法(Insert)、分裂算法(Split)、删除算法(Delete)、搜索算法(Search)。GiST的平衡特性由它的插入算法、分裂算法、删除算法保证。搜索算法是输入一个谓词q,然后对树进行搜索,返回满足谓词q的所有记录。插入算法是在GiST中选择一个合适的位置,将(key,ptr)插入到 GiST中。删除算法是将(key,ptr)从 GiST中删除。为实现上述操作,类型的定义者和开发者还必须向数据库系统注册并且实现如下方法:a)Consistent(E,q):输入一个Entry E=(p,ptr)以及一个查询谓词q,如果 pq为 false,则返回false,否则返回true。系统调用GiST的搜索算法时,需要调用此函数,用来确定满足用户谓词q的记录是否在En2try E.ptr所指向的子树中。b)Uni on(P):输入一个Entry的集合P=Ei|Ei=(pi,ptri),i=1,2,n,返回一个谓词r,其中r=p1p2 pn。系统调用GiST的分裂和合并算法时要调用此函数,来进行内结点之间的合并。c)Co mp ress(E):输入一个Entry E=(p,ptr),返回一个Entry E=(,ptr),其中 是 p的压缩形式。将谓词原封不动地存储在磁盘上可能会浪费空间,此函数的作用是:将 GiST中的谓词压缩后存储在磁盘上。d)Decompress(E):输入一个Entry E=(,ptr)其中 是 p的压缩形式,返回一个Entry E=(r,ptr),其中p r。此函数的作用是:将压缩的GiST在内存中解压缩。e)Penalty(E1,E2):输入 2个 Entry E1=(p1,ptr1),E2=(p2,ptr2),返回一个将E2插入到以E1为根的子树中所带来的惩罚值。惩罚值越小越好。系统调用GiST的分裂和插入算法时要调用此函数。插入时,在GiST中为插入的Entry选择一个较优化的位置。分裂时,在 GiST中为分裂的内结点的另一半选择一个较优化的位置。f)PickSplit(P):输入一个Entry集合 P=Ei|Ei=(pi,ptri),i=1,2,M+1,把 P分裂成2个集合P1和 P2,每个集合中的Entry数目大于等于kM。系统的分裂算法将调用此函数,用来分裂一个Entry数目大于 M 的内结点。6 空间数据库的高维索引在某些应用,比如基于内容的检索或者文本索引中,维数可能很大(几十维是很常见的)。对这些高维数据进行索引很困难,需要新的索引技术。例如当在多于12维的数据集进行单个点的搜索时,顺序扫描就比 R树索引扫描要快。对高维数据集合进行最邻近查询是最常见的查询。对于高维数据存在这样一个潜在的问题:如果高维数据分布的比较广泛,当维数d增加时,到最近邻居的距离(从任何给定的查询点开始)变得越来越接近于到最远的点的距离。在这种情况下最邻近搜索是没有意义的。在许多应用中,可以对高维数据进行索引而不会出现上面谈到的问题。最好在对高维数据进行最邻近查询之前,检查高维数据集合来保证最邻近查询是有意义的。这里给出一种检查的方法:随机地产生一些样本查询,测量每个样本查询中的查询点到最近点和最远点的距离,然后计算这些距离的比率,接下来取这些比率的平均值。如果这个平均值接近于1,则可以断定最邻近查询是没有意义的。距离查询点最近点的距离和最远点的距离的比率被称为数据集的对比度。通过上述方法可以测量出一个数据集的对比度。在需要最邻近查询的应用中,首先应当通过数据的经验测试来保证数据集较小的对比度。参考文献:1BECKMANN N,KR IEGEL H P,SCHNEIDER R.The R3tree:An efficient and robust accessmethod for points and rectanglesA.Proc ACMSIG MOD ConfOn theManagement of Data C.1990.2BERCHTOLD S,BOHM C,KR IEGE L H P.The pyramid-tree:B reaking the curseof dimensionalityA.In ACM SIG MOD Conf On theMan2age ment of Data C.1998.3BEYER K,G OLDSTE IN J,RAMAKR ISHNAN R.W hen is“nearest neighbor”meaningful?A.Proc Int Conf on Database Theory C.19991217-235.?292?黑 龙 江 大 学 自 然 科 学 学 报 第 22卷?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -4THOMAS BR I N KHOFF,HANS-PETER KR IEGEL,RALF SCHNEIDER.Comparison of App roximations of ComplexObjects Used for App roxi2mation-basedQuery Processing in Spatial Database Syste m s J.ICDE,1993,40-49.5FALOUTSOS C.SearchingMulti media DatabasesM.Content Kluwer Academ ic,1996.6CHR ISTOS FALOUTSOS,SHAR I ROSEMAN.Fractals for Secondary Key Retrieval J.P ODS,1989,247-252.7M ICHAEL FREESTON.TheBANG File:A New Kind of Grid File J.SIG MOD Conference,1987,260-269.8VOLKERG AEDE,OL IVER GNTHER.Multidi mensional AccessMethods J.ACM Comput Surv,1998,30(2):170-231.9JONATHAN G OLDSTE IN,RAGHU RAMAKR ISHNAN,UR I SHAFT,et al.ProcessingQueries By L inear Constraints J.P ODS,1997,257-267.10ANTON IN G UTTMAN.R-Trees:A Dynamic Index Structure for Spatial Searching J.SIGMOD Conference,1984,47-57.11 JOSEPHM HELLERSTE IN,JEFFREY F NAUGHT ON,AV I PFEFFER.Generalized Search Treesfor DatabaseSyste ms J.VLDB,1995,562-573.12JOSEPHM HELLERSTE IN,EL IA S KOUTSOUP IA S,CHR ISTOS H.Papadimitriou:On the Analysis of Indexing Sche mes J.P ODS,1997,249-256.13MARCEL KORNACKER,MOHAN C,JOSEPHM HELLERSTE IN.Concurrency and Recovery in Generalized SearchTrees J.SIG MOD Con2ference,1997,62-72.14DAV ID B LOMET,BETTY S ALZ BERG.The hB-Tree:A MultiattributeIndexingMethod with Good Guaranteed Perfor mance J.ACM TransDatabase Syst,1990,15(4):625-658.15 JRG N IEVERGELT,HANS H INTERBERGER,KENNETH C SEVCIK.The Grid File:An Adap table,Symmetric Multikey File Structure J.ACM TransDatabase Syst,1984,9(1):38-71.16JOHN T ROB INS ON.The K-D-B-Tree:A Search Structure For Large Multidi mensional Dynamic Indexes J.SIG MOD Conference,1981,10-18.17HANAN S AMET.The Quadtree and Related Hierarchical Data Structures J.ACM Comput Surv,1984,16(2):187-260.18HANAN S AMET.TheDesign and Analysis of Spatial Data StructuresM.Addison-W esley,1990.19ROGER W EBER,HANS-JRG SCHEK,STEPHENBLOTT.A Quantitative Analysis and Performance Study for Sim ilarity-SearchMethods inHigh-D imensional SpacesJ.VLDB,1998,194-205.20OUR IWOLFSON,PRAS AD SISTLA A,BO XU,et al.DOM I NO:Databases forMoving Objects tracking J.SIG MOD Conference,1999,547-549.21郭龙江,李建中,张兆功.基于记录分布的并行一般搜索树:RD-GiST J.计算机科学,2002,29(8.增刊A):263-266.Index ing techn iques in spatial da taba sesG UO Long2jiang1,2,L IJian2zhong1,2(1.College of Computer Science and Technology,Harbin Institute and Technology,Harbin 150001,China;2.College of Computer Science and Technol2ogy,Heilongjiang University,Harbin 150080,China)Abstract:Due to a great quantity of data in spatial databases,s o in general the costof query in s patial databasesishigher than in relational databases.Especially,when there are s ome functions,in predicateof query,which dealwith s patial data,the costof computing thesefunctions is higher than the cost of comparing strings and numericalvalues.If query strategy is to scan sequentially s patial data,then the efficiency willbe very low.For improvingquery efficiency,it is necessaryto adopt s patial indexing techniques.Indexing techniques in s patial databaseshavegradually caused the attentions of many people.Research advanceof indexing techniques for s patial databasesissummarized,and then four new andoften used indexing methods,including R-tree,K-D-tree,Quad tree andGeneralized searchtree,are introduced.Finally,it is pointed out that the high dimensional index is a hot researchfield in s patial databases.Key words:s patial data;s patial databases;s patial index;high dimensional index?392?第 3期郭龙江等:空间数据库的索引技术?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -