（计算机软件与理论专业论文）基于rtree的高维索引结构研究.pdf

论文题目： 专业： 硕士生： 指导老师： 基于r - t r e e 的高维索引结构研究 计算机软件与理论 舒然 汤庸教授 摘要 随着互联网和多媒体技术的迅猛发展与普及，人们可以通过计算机轻易地 接触并获取到大量有用的数据。如何对大量数据对象进行有效检索成为了计算 机应用中的一个非常重要的研究课题，数据库技术中的索引结构正是为了解决 此问题而出现。 传统的索引结构( 如b t r e e 等) 可以很好的解决单维数据的检索问题，然 而现在接触到的数据大部分属于高维数据。而由于高维数据自身的无序性与复 杂性等特点，传统的索引结构无法直接对其进行处理，所以必须建立高维索引 来进行管理。自从g u t t m a n 提出了基于树形结构的r - t r e e 后，相关学者纷纷在 此基础上进行进一步的研究，例如在此基础上提出的r 幸- t r e e 等。 本文在对r - t r e e 族以及k d b t r e e 族索引结构研究的基础上，对r 霉一t r e e 在 处理点数据方面进行了改进。首先分析了r * - t r e e 在处理点数据上的弱势以及改 进必须解决的问题；接着在r 幸t r e e 结构的基础上提出了一种新的高维点访问方 法p p r - t r e e ( p e r f e c tp o i n tr - t r e e ) 。该方法的基本结构基于r 一t r e e ，但是在分裂 算法中结合p e r f e c tk d b t r e e 中自上而下分裂的思想而提出节点重构技术，可以 有效减少节点问的重叠区域；另外，在压缩节点信息方面，p p r - t r e e 引入了有 效维机制，增加了高层节点的扇出，可以有效降低树高。最后，通过实验验证 了p p r - t r e e 在全部测试维的几乎所有分布中范围查询性能优于r 宰，t r e e ， k d b 。t r e e 以及p e r f e c tk d b t r e e ，数据点查询性能优于r 母t r e e ；并且，在维护 代价方面，相对r 宰一t r e e 并没有太大加重，但是物理利用率得到很大提高。 关键字：高维数据、索引结构、r - t r e e 、有效维、自上而下分裂 t i t l e ：t h er e s e a r c ho f m u l t i d i m e n s i o n a li n d e xs t r u c t u r eb a s e do nr - t r e e m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：s h ur a n s u p e r v i s o r ：p r o f e s s o rt a n gy o n g a b s tr a c t i nr e c e n ty e a r s ，p e o p l ec a l le a s i l ya c c e s saw e a k ho fu s e f u ld a t av i ac o m p u t e r , d u et ot h es w i r la n dv i o l e n td e v e l o p m e n to fi n t e m e ta n dm u l t i m e d i at e c h n o l o g y t h e r ei sas t r o n gn e e df o rt h er e s e a r c h e r st op r o p o s es o m ea d v a n c e da n de f f e c t i v e m e t h o d o l o g i e st or e t r i e v es u c hah u g ea m o u n to fd a t a ，a n dt h er e s e a r c ho fi n d e x s t r u c t u r ei nd a t a l ：i a s ec o m e sf o r t hf o rt h i sr e a s o n s i n g l ed i m e n s i o n a ld a t ac a nh er e t r i e v e de f f i c i e n t l yb ye m p l o y i n gt r a d i t i o n a l i n d e xs t r u c t u r e ( e g b - t r e e ) ，w h i l ei ti sn o tf e a s i b l ef o rt h em u l t i d i m e n s i o n a ld a t a ， w h i c hi sp o p u l a ri np e o p m sl i v e s t h i st y p eo fd a t ai sd i s o r d e ra n dc o m p l i c a t e d ，a n d c a nn o tb er e t r i e v e db yt r a d i t i o n a li n d e xs t r u c t u r ed i r e c t l y , s ot h er e s e a r c ho f m u l t i d i m e n s i o n a li n d e xs t r u c t u r ec o m e si n t ou r g e n t s i n c et h er - t r e e ，w h i c hi sa t r e e b a s e ds t r u c t u r e , i sp r o p o s e db yg u t t m a n , i th a sa t t r a c t e dm a n yr e s e a r c h e r s i n t e r e s t t h e r ea r el o t so ff u r t h e rr e s e a r c hb a s e do nr - t r e e ，s u c ha sr 乖- t r e e t h i st h e s i si m p r o v e st h ep e r f o r m a n c eo fr * - t r e e ，i nt h er e s p e c to fz e r o s i z ed a t a p r o c e s s i n g ，b yd r a w i n gl e s s o n sf r o mt h er e s e a r c ho fr - t r e ea n dk d b - t r e e i nt h e b e g i n n i n g ，t h ew e a k n e s so fr 母。t r e ew h e np r o c e s s i n gp o i n td a t ai sd i s c u s s e d ，t h e na n e w l yp o 砬a c c e s sm e t h o d o l o g yp p r t r e e ( p e r f e c tp o 硫r - t r e e ) i sp r o p o s e d t h i s a l g o r i t h mi sb a s e do nr 宰- t r e e ，b u t i ti sd i f f e r e n tf r o ms e v e r a la s p e c t s f i r s t ，i t e m p l o y san e ws p l i ta l g o r i t h m , w h i c hi n t e g r a t e dt h em e r i to fr * - t r e ea n dp e r f e c t k d b t r e e m o r e o v e r , t h i sa l g o r i t h ma d o p t st h em e c h a n i s mo fa c t i v e d i m e n s i o n s ， w h i c hi sh e l p f u lt oi n c r e a s et h em u l t i d i m e n s i o n a ln o d e s f a n o u t ，a sw e l la st ob r i n g d o w nt h e h e i g h to ft r e e s t r u c t u r e t h ee m p i r i c a lr e s u l t sh a v e p r o v e d o u r m e t h o d o l o g y se f f e c t i v e n e s s c o m p a r e dw i t ht h er 宰- t r e e ，k d b t r e ea n dp e r f e c t i i i k d b t r e e ，t h em e t h o d o l o g yi nt h i st h e s i sh a sb e t t e rp o i n tq u e r yp e r f o r m a n c e ，m o r e e f f e c t i v es t o r a g eu t i l i z a t i o na n dl e s sc o s to fm a i n t e n a n c e k e yw o r d s ：m u l t i d i m e n s i o n a ld a t a ，i n d e xs t r u c t u r e ，r - t r e e ，a c t i v e - d i m e n s i o n s ， t o p d o w ns p l i t 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：鱼丝： 日 期：鲨1 2 生复旦型塑 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：舒熟导师签名：f ，锄 日期：沙叼年岁月加e 1日期：劲哆年多月加日 基于r - t r e e 的高维索引结构研究第1 章引言 1 1 研究背景 第1 章引言 随着互联网的迅猛发展和普及，人们可以通过计算机轻易地获取到大量的 数据，如何存储其中有用的数据以及快速检索到当前需要的数据就成了计算机 应用的个主要问题。为了满足此需求，人们提出了数据库管理技术，通过数 据库中常用到的索引b t r e e ，b + 一t r e e 等，可以方便的对数据进行存储以及检索。 但是，随着计算机应用领域的不断扩张，例如： ( 1 ) 计算机辅助设计( c a d ，c o m p u t e r a i d e dd e s i g n ) ，计算机辅助设计 中的v s l i 设计系统经常需要存储成千上万个用来表示电子元件及 其上层元素的矩形图形i i , 2 ； ( 2 ) 地理信息系统( g i s ，g e o g r a p h i ci n f o r m a t i o ns y s t e m ) ，地理信息系 统中的空间数据，不仅包括了每个地点经纬度、海拔高度以及附近 地标等关键信息，还有相关的地物、地貌特征，多种空间关系的拓 扑信息等【3 】； ( 3 ) 多媒体数据库系统( m m d b s ，m u l t i ，m e d i ad a t a b a s es y s t e m ) ，多媒 体数据库处理的信息既包括大量图像、声音以及视频信息，而且还 包括与信息数据相关的，必须通过特征提取算法从中提出特征矢量 进行处理的信息，例如图像的纹理、图中的物体及其位置、电视镜 头的背景及活动对象等1 4 , 5 】。 当然，还有其他的如机器入学、图像感知、自动导航等各种类型的应用， 它们的共同特点是都对数据的处理要求提升到了二维，三维甚至多维上去，从 而，对多维数据的存储和查询成为了当今数据库领域的一个热点。多维数据可 以是真正的高维数据，比如时态数据库中带有效时间和事务时间的时态信息， 空间数据库中的地理信息等等；也可以是需要频繁查询的多个属性列，在应用 中可以把这些属性列看作是高维数据。 基于r t r e e 的高维索引结构研究第1 章引言 由于高维数据自身的无序性与复杂性等特点【6 1 ，传统关系数据库不能很好地 支持高维数据的存储与检索，使得高维索引无法直接通过传统的索引结构实现， 从而需要引入新的索引机制来提升高维数据的查询效率。所以必须建立高维索 引来解决此问题。 1 2 国内外研究现状 现在的高维索引主要是从四种索引结构演化而来的【7 】：k d t r e e 8 i ，b t r e e ， h a s h i n g ，s p a c ef i l l i n gc u r v e 9 1 。其中又以由k d - t r e e 8 1 演化而来的k d b t r e e 1 0 l 族和由b t r e e 演化而来的r - t r e e l 族应用最为广泛。 k d b - t r e e l l o 】对于均匀分布的数据有良好的查询性能，但对非均匀分布的数 据性能较差。实际应用中多数数据都是非均匀分布的，比如g i s 中的地理数据 大多是聚簇分布。k d b t r e e 具有向下分裂的特性，使得节点数过多，物理利用 率低1o ，1 2 , 1 3 1 。k d b h d _ t r e e 1 4 1 和k d b r , s ) 一t r e e 【1 5 】通过引入首次分裂( f i r s td i v i s i o n ， f d ) 的分裂方法，消除了向下分裂；同时他们都通过去除索引节点中的冗余信 息，提高了节点的扇出。但是由于首次分裂的方法不能保证将节点大约等分， 造成索引节点物理利用率依然低下，而且其查询效率没有得到本质上提高。 p e r f e c tk d b t r e e 1 6 】通过溢出时对节点的重构，避免了向下分裂，大大提高了其 物理利用率( 最高能达到1 0 0 ) ，同时使得索引结构非常紧凑，降低了树高， 提高了查询效率；但其最大的缺点是每次节点的分裂都需要读写该节点子树中 所有子节点，造成维护代价过高，不易控制。 r - t r e e 族索引是多维索引中最为成功的一族【6 ，1 7 ，18 1 ，在一些商业数据库中已 经得到成功的应用，如o r a c l e1 0 9 ，d b 2 等。r - t r e e 是g u t t m a n 等人在8 0 年代 提出的一种平衡树，是b t r e e 在高维上的扩展，对于非均匀分布的数据有着较 好的查询性能，但其只能保证至少5 0 的空间存储利用率。 在r 。t r e e 众多的变种中，r * - t r e e 1 9 】是最有名、效率最高的一种。r 宰一t r e e 同 时支持对零面积数据和非零面积数据对象的处理。而且实验证明，r 书t r e e 对点 数据的处理有着很好的性能【1 7 】。r + 由e e 刚在内部节点中为了避免兄弟节点重叠， 规定同一个对象可以存在于多个节点中，解决了点查询中形成的多条路径查询 2 基于r - t r e e 的高维索引结构研究第1 章引言 问题，但冗余信息导致树高增加，降低区域查询性能。h i l b e r tr - t r e e l 2 1 】利用 h i l b e r t 分形曲线对高维数据进行一维线性排序，进而对树节点进行排序，借以获 得面积、周长最小化的树节点。t v - t r e e f 2 2 1 通过对特殊数据集进行k l 变换 ( k a r h u n e nl o w et r a n s f o r m ) 来对数据的高低维进行分离以及限制节点中的有效 维数( a c t i v e d i m e n s i o n s ) 来提高扇出。b u d d y - t r e e t b l 通过递归的二分空间，避 免了r - t r e e 中节点m b r 的相交，但同时造成其叶子节点不在同一层。x t r e e 2 3 1 通过引入超节点，避免了采用f d 的分裂方法而造成r - t r e e 节点不平衡的情况， 但同时也使其实现和维护变得复杂。c o m p a c tr - t r e e 2 4 1 采用了特殊的分裂算法， 使得节点分离次数明显减少，从而减低了维护的开销，并且其空间存储利用率 可以达到1 0 0 ，但是其查询性能只和r 。t r e e 相仿。a t r e e 2 5 】通过引入虚拟最小 外包矩形v b r 和二进制压缩，有效提高了节点扇出。另外，基于r t r e e 的变体 还有很多，例如对数据对象表达方面变换的p t r e e 2 甜，c e l l t r e e 2 7 1 ，s r 骶e 【2 8 1 ， s p h e r e t r e e l 2 9 】；借鉴了位图索引的思想b i t m a pr t r e e s 3 0 1 ，适用于主存的索引 d r - t r e e i 鲥j 等。 1 3 本文的研究思路 从前面的论述中可知，目前高维索引的查询应用越来越广泛，只要查询效率 有所提高，对于大规模的查询来说都是有意义的。r - t r e e 族的索引结构在商业 数据库宁的成功应用表髓其具有优越性1 6 1 ，故本文选择r 幸一t r e e 作为改进的基本 结构。影响r 串一t r e e 效率的两个主要问题是节点间区域重叠f 3 2 1 与处理高维数据时 扇出交小。所以本文主要从这两个方面对舻一t r e e 进行改进。 本论文的主要工作及创新点可以总结为以下两个方面： l 、在r 事一t r e e 结构的基础上，弓l 入p e r f e c tk d b t r e e 插入算法中自上而下分 裂方法的思想。 r 幸一t r e e 在处理高维数据时，由于r * - t r e e 在内部以及叶子节点允许区域相交， 所以在插入数据的过程中可能会造成节点问区域的相互重叠，而且当处理的数 据的维度越高时，重叠的区域成级数倍增长，会因此而影响查询的效率；而在 零面积数据的条件下，节点间区域的相交是完全可以避免的。自上而下的分裂 3 基于r t r e e 的高维索引结构研究第1 章引言 方法可以有效解决此问题。 2 、在r * - t r e e 结构的基础上，引入有效维的机制。 经过大量实验发现，在高维情况下，节点中所有维上的值并不是都同样有 效的，即数据在某维的值在该维上不具有区分能力，比如，所有孩子在该维上 的值均几乎跨越整个值域。为了去除高维下节点的冗余信息，引入了有效维数 ( a c t i v e 。d i m e n s i o n s ) 的机制，并对节点中的m b r 进行量化并将其压缩为二进制 的值，这样可以有效压缩空间，增加扇出，同时降低了树高。在t v 二t r e e 【捌中的 有效维概念并没有具体提及如何处理有效维的动态改变以及何时调整节点有效 维等问题，而本文则在此方面进行了具体分析与设计。 1 4 论文的组织结构 本文一共分为五章，组织结构如下： 第1 章，介绍了高维索引的研究背景和意义，并提出本文工作的研究思路 及研究目标。 第2 章，首先介绍了多维索引中的r - t r e e 与k d b t r e e ，接着介绍了在它们 基础上进行改进的r 术一t r e e 与p e r f e c tk d b t r e e 。 第3 章，首先分析了r 孝t r e e 与p e r f e c tk d b t r e e 在处理点数据上的不足之 处，接着在此基础上进行改进，进而提出了新的索引结构p p r - t r e e 。 第4 章，将新提出的索引结构p p r - t r e e 与r * - t r e e 、k d b t r e e 以及p e r f e c t k d b t r e e 进行二维以及高维上的性能比较，并得出相关的结论。 第5 章，对全文进行总结，针对本文工作中的不足，提出了进一步的研究 方向。 4 基于r - t r e e 的高维索引结构研究 第2 章几种高维索弓l 的介绍 第2 章几种高维索引的介绍 本章将对应用广泛的几种高维索引进行介绍与分析。主要包括以数据进行 划分的索引结构r t r e e ，以空间进行划分的索引结构k d b t r e e ，以及在它们基 础上进行改进的r 宰t r e e 和p e r f e c tk d b t r e e 。 2 1 索引结构r - t r e e r t r e e 是由g u t t m a n 在8 0 年代提出的数据结构，是目前应用最广泛的索引 结构之一【6 ，1 7 ，18 1 。r t r e e 是在b t r e e 基础上扩展的平衡树，和b t r e e 一样，r t r e e 的数据也是存储在叶子节点上。 2 1 1r t r e e 的结构 r - t r e e 【1 1 】的结构如下： 叶子节点具有如下形式： ( d a t a ，p o i n t e r ) ； 其中d a t a 是实际的数据点或者矩形，p o i n t e r 是指向存储数据的指针。 内部节点具有如下形式： ( r e c t a n g l e ，p o i n t e r ) ； 其中r e c t a n g l e 是包含了子节点的所有数据的m b r ，即是最小包围矩形( 如 图2 1 所示) ，p o i n t e r 指向所有的孩子节点。 r - t r e e 满足以下条件，其中，肘是节点所容纳的最多元素，m 是元素个数的 最小值，并且m = m 2 ： ( 1 )除了根节点，所有的节点必须有m 到m 个元素； ( 2 )根节点如果不是叶子节点，则至少有两个孩子节点； ( 3 )所有的叶子节点都是处于同一层上。 5 基于r t r e e 的高维索引结构研究 第2 章几种高维索引的介绍 ( a )( b ) ( a ) e 为矩形a 、b 、c 、d 的m b r ( b ) f 为包含里面所有点的m b r 图2 1 两种类型的m b r 按照定义，r - t r e e 应该是具有如图2 2 所示结构的树。 ( b ) ( a )区域内遇有一些矩形数据 ( b ) 在( a ) 中的数据集上建立起来的r - t r e e 图2 - 2r t r e e 的一个示例 6 基于r t r e e 的高维索引结构研究第2 章几种高维索引的介绍 上面是r - t r e e 的一个示例，其中m = 3 ，数据包括彳，e c ， ，等9 个矩形数据， 根节点是包括所有这9 个矩形的m b r ，内部节点有2 个，左边的内部节点包括 a b e g 四个矩形，而右边的内部节点包括c d f h i 五个矩形，最下面的是叶子节 点。 2 1 2r - t r e e 的插入算法 r - t r e e 的插入算法可以分成主要的两个部分，首先是查找过程，由自上而下 的路径一直查找到叶子节点；然后是自下而上地由叶子节点调整到根节点，最 终完成整个插入的过程。 自上而下的查找过程： ( 1 ) 从根节点开始，对每个子节点进行比较，选择需要增加m b r 面积最 小的子节点继续进行查找； ( 2 ) 当查找到叶子节点时，此叶子节点为新元素的插入节点； ( 3 ) 当查找到的是内部节点时，一直重复查找步骤；当遇到所需要增加的 面积值相等时，取增加后m b r 值小的节点，如果还是相等，可以随 便选择一个。 自下而上的调整过程： 自下而上的调整过程又主要分成两种情况，一种是不需要分裂的情况，当 上述查找过程找到的节点可以容纳多一个元素的时候就出现这种情况，这时调 整只需要沿着查找的路径往上调整各个内部节点的m b r ，一直调整到根节点就 完成插入过程；另外一种则是需要分裂的情况： ( 1 ) 当查找到的叶子节点无法再容纳新元素时，叶子节点就必须分裂，即 叶子节点中包括新元素在内的所有元素分成两个叶子节点； ( 2 ) 若上一级的节点可以容纳分裂出来新的节点则不需要再分裂，继续完 成上面的不需要分裂的情况的处理即可； ( 3 ) 否则，在分裂的同时调整当前节点的m b r ，并且分裂在内部节点中 继续往上传递，直到根节点； ( 4 ) 当根节点不需要分裂的时候，插入完成。否则，根节点分裂，树高增 加。 上面提到的分裂算法，可以选择平方的算法和线性的算法，或者其他的任 7 基于r - t r e e 的高维索引结构研究第2 章几科高维索引的介绍 意算法，如文献【3 3 】、【3 4 和【3 5 】提出了其他的分裂方法。分裂方法应当能把被 分裂节点的所有元素尽可能平均而又使得重叠区域少。当满足上述条件的程度 越高时，r - t r e e 在查询的时候效率就越高。 2 1 3r - t r e e 的查询算法 r t r e e 的查询算法和b t r e e 类似，都是自上而下的搜索，但是由于r t r e e 的内部节点允许重叠，所以搜索的时候路径可能并不唯一。而多条路径的搜索 是影响查询效率的重要因素，如果能保证每次查询的路径都近似为一条的时候， 那么就可以达到很高的查询效率。 r - t r e e 的查询分为点查询和区域查询，但是它们的搜索过程相类似。 ( 1 ) 从根节点开始，判断需要查询的点或者区域是否处于根节点的m b r 中，如果没有，则所要查询的目标不存在；如果点处于根节点的m b r 中，或者查询区域与根节点的m b r 相交，则转到相应的子节点； ( 2 ) 由于查询点或者查询区域所处在的位置可能是几个子节点重叠的区 域，这样的话就要分别从这几个子节点来按照上面的步骤继续往下查 询内部节点； ( 3 ) 如果当前节点不包括查询点或者与查询区域没有相交的区域，则说明 当前路径查询不到目标； ( 4 ) 如果查询路径一直到叶子节点。则读取当前叶子节点的所有数据，判 断是否存在目标查询点或者处于查询区域。 2 1 4r - t r e e 的删除算法 r - t r e e 的删除主要分成两个步骤进行。首先，利用上述的查询算法，去查找 所需要删除的元素所在的叶子节点，当这样的叶子节点不存在时，则证明原数 据中没有包含所要删除的元素，删除过程完成；否则，当查找过程返回含有所 需要删除的元素的叶子节点时，删除此元素，并对r - t r e e 进行自下而上的必要 的调整： ( 1 ) 当删除元素并没有使得叶子节点的元素个数少于最小值m 时，只需 要往上调整各内部节点的m b r 即可； ( 2 ) 否则，在上一级的节点中把当前节点所处的子节点删除，并继续往上 重复此步骤，一直到当前节点的元素个数大于等于最小值研，或者直 8 基丁r - t r e e 的高维索引结构研究第2 章几种高维索引的介绍 到根节点； ( 3 ) 最后，把所有刚删除的非目标节点重新插入到r t r e e 中。 需要注意的是最后的节点重新插入过程。由于此前删除的节点处于不同的 层中，所以在重新插入的时候，也要插入到相应的层中，这样才能保证所有的 叶子节点处于同一高度中。插入结束后，如果根节点只有一个孩子节点，则这 个孩子节点作为根节点，即树的高度降低。 2 2 索引结构k d b - t r e e k d b t r e e 是从k d t r e e j 8 1 和b - t r e e 相结合的数据结构，兼备了k d t r e e 可以 处理高维数据与b t r e e 可以处理储存于外存的数据的特点。 2 2 1k d b t r e e 的结构 k d b 树的结构如下： 叶子节点具有如下形式： ( d a t a ，l o c a t i o n ) ； 其中d a t a 是实际的数据点，l o c a t i o n 是指向存储数据地方的指针。 内部节点具有如下形式： ( r e g i o n ，p o i n t e r ) 其中r e g i o n 是当前节点的区域，p o i n t e r 指向所有的子节点。在这里，r e g i o n 所代表的区域是对空间的分隔，即同一层次的节点的r e g i o n 都是不相交的，而 且它们按照所在位置并起来的话正好是上一级节点的r e g i o n 。由于分割方式的 限制，r e g i o n 在二维和三维的时候对应的分别是矩形和长方体，其他更高维的 以此类推。 k d b t r e e 具有以下属性： ( 1 ) 叶子节点都处于同一层中，并且没有一个内部节点包含空指针，或 者内部节点是空的； ( 2 ) 所有同一层节点的区域都是不相交的，并且它们并起来可以组成一 个完整的区域； ( 3 )内部节点的区域都是它的孩子节点区域的并，如果孩子节点是叶子 9 基于r - t r e e 的高维索引结构研究 第2 章几种高维索引的介绍一 节点，则内部节点应该包含所有孩子节点的数据点； ( 4 ) 如果根节点是内部节点，那么它的区域是包括数据点定义域的空间。 按照定义，k d b t r e e 应该是具有如图2 - 3 所示结构的树。 图2 - 3k d b t r e e 的一个示例 2 2 2k d b t r e e 的查询算法 k d b 树的查询算法可以分为两种类型，一种是数据点的查询，由于数据点 都是唯一的只属于某个区域，而且各个节点的区域是不重叠的，所以数据点的 查询路径只有一条，就是从根节点到叶子节点的路径，同层次的每个内部节点 只会出现一次；另外一种是区域查询，由于查询的区域可能与多个同层节点的 区域相交，所以查询路径可能不止一条，只要与查询区域相交的节点的区域都 要遍历一遍。 k d b 树的数据点和区域查询类似，查询过程如下： ( 1 ) 从根节点开始，如果根节点是叶子节点，则读取所有数据点，判断是 否含有要查询的点或者是否包含在所查询的区域内。否则，由于查询 点和区域都包含在定义域中，应该对根节点的孩子节点进行查询； 1 0 基于r - t r e e 的高维索引结构研究第2 章几种高维索引的介绍 ( 2 ) 判断查询点或者查询区域与哪些节点的区域相交，如果有相交的区 域，则从这些子节点继续往下查询内部节点； ( 3 ) 如果当前节点与查询点或者与查询区域没有相交，则说明当前路径查 询不到目标，当前的查询路径可以停止； ( 4 ) 如果查询路径一直到叶子节点。则读取当前叶子节点的所有数据，判 断是否存在目标查询点或者处于查询区域。 2 2 3k d b t r e e 的插入算法 k d b 树的插入涉及最多的步骤是分裂，分裂又可以分为两种，一种是叶子 节点的分裂，另外一种是内部节点的分裂。对于叶子节点的分裂，选定一个分 裂的维度和在这个维度上的值进行分裂就可以了；而对于内部节点的分裂，在 选定分裂的维度和在这个维度上的分裂值后，对当前节点的区域进行分裂，有 可能造成其孩子节点也进行分裂。所以，对内部节点的分裂不是简单的由下而 上的过程，当上级的节点分裂会对下级的节点造成影响时，必须重新递归下去， 直到当前节点没有受到影响或者叶子节点为止。 - i r - i- - -i。- - - -i - - i - - - - ( a ) l i d i - - 。 ( b ) ( a ) 叶子结点中的分裂 ( b ) 内部结点的分裂 图2 - 4k d b t r e e 中的两种分裂 叶子节点分裂后会形成左右两个叶子节点，内部节点分裂后，属于分割线 摹于r t r e e 的高维索引结构研究第2 章几矛l t 高维索引的介绍 两边的区域分别属于新形成的左右节点，而被分割线横跨的区域，按照处于分 割线的位置，也分别属于新形成的左右节点。在对叶子节点或者内部节点进行 分裂的时候，通常可以采用维度循环选择或者固定某一维优先选择来进行。 k d b t r e e 中的叶子节点与内部节点分裂如图2 - 4 所示。 k d b 树的插入过程可以描述如下： ( 1 ) 当不存在根节点时，创建一个叶子节点作为根节点，并插入数据点； 否则，将按照查询过程找到数据点应当插入的叶子节点； ( 2 ) 把数据点插入到找到的叶子节点中，如果没有溢出，则插入结束；否 则，将调用分裂过程，并将分裂过程形成的新的左右两个节点插入到 父节点中； ( 3 ) 如果父节点也溢出，则分裂过程往上传递，一直到根节点或者不用分 裂的节点为止； ( 4 ) 如果分裂到根节点，则新创建一个节点作为根节点，其孩子为分裂形 成的左右两个节点。 2 2 4k d b t r e e 的删除算法 k d b t r e e 的删除主要是参考了b - t r e e 的删除过程。b t r e e 删除的时候，当 前节点如果元素个数低于下界的时候，其中一个经常出现的操作是和相邻节点 合并，这个过程在一维的情况下是没有任何问题的，因为维的数据按照大小 次序来合并成一个节点总是可以操作的，但是，在二维或者更高维的情况下就 不适用了，因为相邻的区域不一定能够合并。这样，k d b t r e e 的删除过程就和 b t r e e 的有点区别。 k d b t r e e 的删除算法如下： ( 1 ) 首先，按照查询过程，找到需要删除的数据点，将此数据点删除。如 果当前节点的元素个数还大于下界，则删除结束； ( 2 ) 否则，要对当前节点进行处理。先上升到当前节点的父节点，然后找 出同一个父节点的所有可以与当前节点合并的子节点。可以合并的子 节点可能是一个或者多个，甚至是包括了所有的子节点；。 ( 3 ) 合并上一步骤中找到的可以合并的节点，并对合并后的节点进行传递 分裂，直到分裂后所有的节点都没有溢出的情况存在； 1 2 基于r - t r e e 的高维索引结构研究第2 章几种高维索引的介绍 ( 4 ) 用分裂后的新节点代替原来的节点，删除完成。 2 3r - t r e e 与p e r f e c tk d b - t r e e 2 3 1r 棠- t r e e r 宰t r e e 1 9 1 是在r - t r e e 基础上的改进。对r - t r e e 的研究发现，影响效率的一 些参数有： ( 1 ) 节点的m b r 面积尽量小。m b r 面积小意味着会减低了同层次节点 m b r 相交的可能性； ( 2 ) 减小内部节点的m b r 的相交区域。相交区域变小，查询时候将避免 过多的分支，从而提高查询效率； ( 3 ) 节点的m b r 的周长尽量小。当一个矩形面积相等时，形状为正方形 时周长最小。使周长尽量小的要求可以保证节点的m b r 都近似于正 方形。在构造树的过程中，正方形的m b r 更容易安放，往往有利于 内部节点的m b r 的减小；而且，当插入新元素时，所要增加的面积 也相对小； ( 4 ) 空间的利用率要尽量高。利用率高意味着树的高度相对比较低，这样 从根节点到叶子节点的路径较短，查询的效率也相对高； 当然，上述几个要求不可能同时达到。当满足节点m b r 尽量小和减小内部 节点的m b r 相交区域时，对元素个数的选择不能得到充分保证，这样空间利 用率就得不到保证。而当节点的m b r 面积小的同时，是有利于减少内部节点 m b r 相交区域的，但是却对m b r 的形状随意选择，保证不了m b r 的周长。 同时，周长尽量小的话也不利于提高对空间的利用率。当进行足够大的区域查 询时，最重要的因素是空间利用率，因为这时的查询无论如何都要遍历多数的 分支路径，所以影响比前几个因素更加明显。 r 枣t r e e 在综合考虑了上述因素的基础上，对r - t r e e 的三个主要方面进行改 进，前面两个改进分别是插入过程中子树的选择的改进和插入过程中的溢出分 裂方法改进。 r 枣一t r e e 的插入子树选择相对于r - t r e e 来说，其特点是在内部节点选择过程 1 3 基于r t r e e 的高维索引结构研究一第2 章几种高维索引的介绍 中考虑的顺序首先是插入新元素导致相交的区域，其次是增加的商积，接着是 增加后的面积，而叶子节点的选择过程中主要是考虑插入新元素增加的面积， 其次是增加后的面积。 而在分裂过程方面，r 誊t r e e 的分裂分为两个步骤，首先选择分裂的维，接 着选择在此维上的分裂值。选择维的时候，先按照各个维把所有矩形按当前维 上的值先小值的边再到大值的边的由d , n 大排列，然后在中间选择一个分割点 的进行分隔，在分成的m - 2 m + 2 个( 分成两对，每一个至少有m 个元素，最多 肘个元素) 有效对中，选出周长最小值，然后在所有的值中确定维；确定维之 后，还是按照刚才的分对方法，找出相交区域最小的组合，如果相等，则找出 面积最小的组合。 r t r e e 和r * - t r e e 都有共同的特点，当插入元素的顺序不同时，得到的索引 一般也不一样，往往某些插入顺序会导致相对较差的查询效率。所以，r 拳一t r e e 的另外一个改进之处就是在插入新元素的过程中强制重新插入某些旧元素。 r 书t r e e 在插入新元素的时候，如果将要插入的节点已经满了，不是一开始 就调用分裂的步骤，而且按照某种规则，找出离原节点中心比较远的元素，重 新插入这些元素。其中，处理过程中以层数为参数，第二次出现要溢出的时候 才调用分裂。这样，可以减少分裂的次数，而且还会适当的减小了相交的区域， 提高了磁盘的利用率，节点的形状更加接近正方形，更利于查询效率的提高。 2 3 2p e r f e c tk d b t r e e p e r f e c tk d b t r e e m 】是在k d b t r e e 的基础上进行改进的。 在k d b 树的插入新元素过程中，如果找到的被插入的叶子节点已满，这时 就要进行分裂，而分裂时为了保持兄弟节点间的平衡，往往导致上级的节点也 在同一维上进行分裂，上级节点的分裂又会最终递归到叶子节点上，这样的过 程不但冗杂，而且频繁的对叶子节点进行分裂会使得叶子节点的数量大量增加， 导致磁盘的空间利用率低下。而且，数据的插入顺序不同会对k d b - t r e e 的结构 造成很大影响，往往其中几个元素换一个顺序就可以得到更好结构的k d b t r e e 。 所以，怎样能够避免过多的分裂以提高磁盘空间利用率以及如何减低数据插入 顺序对k d b t r e e 整体结构的不良影响，是p e r f e c tk d b t r e e 对k d b t r e e 进行改 进的主要问题。 1 4 基于r t r e e 的高维索引结构研究第2 章几种高维索引的介绍 p e r f e c tk d b t r e e 中的兄弟节点间的调整如图2 5 所示。 图2 5p e r f e c tk d b t r e e 中兄弟节点间的调整示例 针对上面提出的两个问题，p e r f e c tk d b t r e e 树在k d b t r e e 的基础上做出了 改变。当插入薪元素的时候，如果叶子节点没满，则还是按照原算法进行插入， 但是，如果叶子节点是满的话，可以分为以下几种情况来分别处理： ( 1 ) 当待插入的叶子节点满了，但是此叶子节点的其他兄弟节点未满的时 候，把当前节点中最靠近未满兄弟节点的个元素并入兄弟节点，或 者可以理解为直接调整原来的分割线，这样当前节点还处于满的状 态，而兄弟节点处于未满或者满的状态，避免了分裂的发生； ( 2 ) 当待插入的叶子节点满了，而且此叶子节点的所有兄弟节点也满了， 但其父亲节点的孩子数未满的时候，增加一个叶子节点，按照现在的 孩子数对所有的元素进行重新分配，按照大约平均的方式将相邻的元 素放置在同一节点里，这样操作只是增加了一个内部节点，并不是传 统意义上的分裂，所以此操作不会有往上传递的过程； ( 3 ) 当待插入的叶子节点满了，而且此叶子节点的所有兄弟节点也满了， 并且其父亲节点也容纳的孩子数己满的时候，只能进行分裂了。分裂 的方法是，增加一个叶子节点，按照现有的节点数对所有的元素进行 重新分配，按照大约平均的方式将相邻的元素放置在同一节点里，在 父亲节点增加一个元素对应新增加的节点，由于父亲节点已经容纳不 了更多的元素了，所以父亲节点分裂成两个节点，分别对应相应的区 域。并且分裂需要往上传递。 1 5 基丁r - t r e e 的高维索引结构研究一第2 章几种高维索引的介绍 这种分裂的方法避免了由于叶子节点分裂导致内部节点分裂后，还要往下 传递的过程，而且保证了内部节点中尽可能所有的分支数都接近最大数目，这 时整个结构的节点数量是最少的，磁盘的空间尽可能得到利用，进而提高了磁 盘的空间利用率。 2 4 小结 本章主要介绍了两种类型的高维索引，分别是以数据划分的索引，其代表 是r t r e e ，和以空间划分的索引，其代表是k d b t r e e 。 通过阐述两种类型的索引的基本结构，以及它们在插入、查询以及删除算 法上的区别，可以了解到它们间的不同思想以及它们在处理不同问题时的优劣 之处。而且，在索引结构的基本结构相同的情况下，影响到性能的最主要算法 是插入算法。插入算法中的各种考虑因素对查询类别的不同有着决定性的影响