（计算机软件与理论专业论文）基于空间分解的路径多维索引查询方法研究与实现.pdf

中山大学硕士学位论文( 2 0 1 0 ) 基于空间分解的路径多维索引查询方法研究与实现 专业：计算机软件与理论 硕士生：陈智孟 指导教师：王若梅教授 摘要 x m l 作为一种数据描述语言，由于其内容与形式分离、易扩展、和易移植 的特点，已经成为广泛应用的数据交换标准。基于x m l 的数据查询十分频繁， 如何提高x m l 数据查询效率也一直是领域研究热点。x m l 数据索引的性能是决 定其查询效率的关键因素，路径多维索引( u n i v e r s a lb + t r e e ，简称u b t r e e ) 是一种将路径转化为空间地址，进而实现对数据进行多维管理的索引结构，由 于其摆脱了原有的路径匹配只能基于字符串匹配的特点，逐渐成为x m l 数据索 引的一个重要实现技术，其中区域查询算法的效率以及区间存储方式是该技术 中的重要研究课题。 目前已实现的具有代表性的x m l 路径多维索引方法是的u b t r e e 方法 ( u n i v e r s a lb + t r e e ) 。l i b t r e e 方法存在两个问题：1 ) 索引树中的节点记录 一个区间，但数据分布的无规律性使得区间内通常只有少量数据点，对数据查 询的效率造成很大影响；2 ) 在数据查询时无法避免对空数据区间的遍历。以上 两个问题显著影响u b t r e e 方法查询的效率。 本文的研究拟对以上两个问题进行改进。首先，针对存储空间使用率不高， 存在大量无数据区间的问题，本文在以区间段存储取代原有的区间分割地址储 存方式的基础上，采用改进的边界区间存储方式对批量数据进行存储，有效提 升了空间的有效利用，并减少了存储结构中对无数据区间的保存开销；其次， 针对数据查询存在的效率问题，本文在t o m a ss k o p a l 等人提出的基于区间相交 性判断的改进d r u 区域查询算法基础上，采用空间分解的方法对查询区域进行 有效的分解，同时建立缓存用于存储公共路径，减少对相同节点的重复访问。 实验结果表明，基于改进数据存储方法的空间分解查询算法在查询效率以及区 间使用率方面都较原u b t r e e 方法有不同程度的提高。 中山大学硕士学位论文( 2 0 1 0 ) 关键词：路径多维索引：x m l 索引：区域查询：空间填充曲线 中山大学硕士学位论文( 2 0 l o ) u s i n gp a t i a ld e cp o s i t i o no nb u b t r cr a n g equeryusing s p a t i a ld e c o m p o s i t i o no nbu b e er a n g eu e r v a l g o r i t h m 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 ：c h e nz h i m e n g s u p e r v i s o r ：p r o f e s s o rw a n gr u o m e i a b s t r a c t a sad a t a - e x p r e s sl a n g u a g e ，x m li sc h a r a c t e r i z e dw i t he a s yp o r t a b i l i t y , f r e e e x t e n s i b i l i t ya n dt h ed i s c r e t i o no fc o n t e n ta n ds t r u c t u r e , a n dt h a tm a k e si tb e c o m ea n i n t e r n a t i o n a ls t a n d a r do fd a t ae x c h a n g e b e c a u s et h ed a t aq u e r yb a s e do nx m li s f r e q u e n t l y , h o wt oi m p r o v et h eq u e r ye f f i c i e n c yi sg r e a tc o n c e r n e d t h ee f f i c i e n c yo f t h ex m l q u e r yi su pt ot h ex m l i n d e x u n i v e r s a lb + - t r e e ( u b t r e e ) a sa nx m l i n d e xt h a tt r a n s l a t e st h eq u e r yp a t hi n t ou n i v e r s a la d d r e s st or e a l i z et h ei n d e x s t m c t u r et h a tm a n a g et h ex m ld a t ai nm u l t i d i m e n s i o n a l a sak i n do fx m li n d e x w h i c hg e tr i do ft h et r a d i t i o n a lm e t h o dt h a tp a t hm a t c h i n go n l yb a s e do nt h es t r i n g m a t c h i n g ，u b t r e eb e c o m e sa ni m p o r tt e c h n o l o g yo fx m li n d e x , t h ec o r e a l g o r i t h m sr a n g eq u e r ya l g o r i t h ma n dd a t as t o r a g ea l g o r i t h mt h e r e 南r eh a db e e n s t u d i e da sa ni m p o r t a n tr e s e a r c hs u b j e c t c u r r e n t l y , a st h er e p r e s e n t a t i v ex m li n d e x , u n i v e r s a lb + 一t r e e ( u b t r e e ) h a s t w om a i np r o b l e m s ：1 ) t h ei n d e xt r e ei n d e x e st h ew h o l eu n i v e r s e ，b u tr e a lw o r m d a t au s u a l l yh a san o n - u n i f c i r i l ld a t ad i s t r i b u t i o n , i ti saw a s t eo ft i m et oi n d e xt h e n o n d a t as p a c e ；2 ) t h er a n g eq u e r ya l g o r i t h mc a n n o ta v o i dt oa c c e s sn o d ew h i c h s t o r et h er e g i o n st h a tl a yo u to ft h er a n g e t h e s ep r o b l e m sa r eg r e a t l yi n f l u e n c e d w i t ht h ee f f i c i e n c yo fi n d e x i nt h i sp a p e r , n e w a l g o r i t h m sa r ei n t r o d u c e dt os o l v et h et w om a i np r o b l e m s f o r t h ef i r s to n e ，t h ei m p r o v e db o u n d i n gu b - t r e e ( b u b - t r e e ) w i l lb eu s e dt oi m p r o v e t h eq u e r ye f f i c i e n c yw h i l ei ts t o r e sz i n t e r v a l sb o u n d i n gt h ed a t as t o r e do rt h e i i i 中山大学硕士学位论文( 2 0 i o ) c o r r e s p o n d i n gp a g e f o rt h es e c o n do n e ，an e wr a n g eq u e r ya l g o r i t h m , b a s e do nt h e i m p r o v e dd r ua l g o r i t h mw h i c hw a sp r o p o s e db yt o m a s ，u s e ss p a t i a ld e c o m p o s i t i o n i i lt h er a n g eq u e r y , w i l lb eu s e dt oi m p r o v et h ee f f i c i e n c y , b e s i d e s b u f f e rl i s tw i l lb e s e tt os t o r et h ep u b l i cp a t h sd u r i n gt h eq u e r yt oa v o i dt h er e p e a ta c c e s so f t h en o d e f i n a l l y , t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ei m p r o v e db u b t r e eb a s e do n s p a t i a ld e c o m p o s i t i o nh a sab e t t e rp e r f o r m a n c et h a nt h ei n d e xp u r p o s e db yt o r n a si n t h ea s p e c to fr a n g eq u e r y k e y w o r d s ：u b - t r e e ，x m li n d e x , r a n g eq u e r y , s p a c ef i l l i n gc u r v e s i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论鬻签名骶 日期缈2 0 年，月自 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 日期2 0 f 哞加厂 脚 月f 日 中山大学硕士学位论文( 2 0 1 0 ) 1 1 研究背景 第一章绪论 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) ，是一种可扩展的置标性语言，又称可 扩展标记语言，从1 9 9 5 年开始发展，在1 9 9 8 年二月发布为w 3 c 的标准，前身 是s g m l ( t h es t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ) 。x m l 的创立是为了解决 h t m l 中存在的不能解决所有解释数据，效能，扩充性、弹性、易读性均不佳 等问题，其用途的焦点是说明数据是什么，以及携带的数据信息【1 1 。 x m l 规范规定了x m l 数据必须满足的条件，其基本的形式是x m l 文档。 从逻辑上讲，一个x m l 文档通常由5 部分组成：声明、元素、注释、字符引 用和处理指令，统称为x m l 数据单元1 2 。 为了从x m l 以及半结构化数据中获取所需要的信息，研究人员开发了许 多查询语言，包括l o r e l ，x m l q l ，x m l - g l ，q u i r ，x p a t h ，x q u e r y 。它们 共同的特征为：采用了正则路径表达式的形式，其本质是捕捉x m l 数据单元 间的结构关系和内容。当在x m l 文档类数据之上处理x p a t h 查询时，借助于 w 3 c 定义的x m l 数据处理的两种接口规范，d o m ( d o c u m e n to b j e c tm o d e l ) 和 s a x ( s i m p l ea p i f o rx m l ) ，处理方式可概括为：顺序读取x m l 文档中的节点； 如果该节点的路径满足x p a t h 中定义的条件( 包括结构关系、测试条件和谓词关 系) ，那么该节点即为x p a t h 查询语句的一个输出【3 】。 基于基本线性表达式的x m l 查询主要存在两个缺陷：1 ) 只能采取周游的 方式在x m l 文档中寻找满足查询语句结构关系的数据单元，即为了获取满足 查询路径的结果，必须周游所有可能的数据单元的标签路径，效率不高；2 ) 对 x m l 中标签路径相同的节点，仍然需要重新遍历它们的路径【4 1 。 研究人员针对x m l 查询存在的两个主要缺陷，提出了x m l 索引，主要分 为两大类：结构摘要类索引和节点记录类索引。 中山大学硕士学位论文( 2 0 1 0 ) 结构摘要类索引的基本思想是对x m l 文档树进行归约，即将具有相同路 径的数据点归为一个数据集合，同时保存该路径，避免了x m l 查询中，对标 签路径相同节点的重复遍历。 节点记录类索引的基本思想是将x m l 文档分解为若干个数据点集，同时 保存每个数据点在x m l 文档中的位置信息。当前主要有两种获取位置信息的 方法：1 ) 节点序号方法( n o d en u m b e r i n gm e t h o d ，有时也称为节点标签方法，n o d e l a b e l i n gm e t h o d ) ；2 ) 节点路径方法( n o d ep a t hm e t h o d ) 5 1 ，对它们的研究成为当前 x m l 索引研究的重点。 1 2 国内外研究现状 x m l 索引的研究主要集中在节点记录类索引方面，节点记录类索引根据位 置信息的不同表现形式，产生三种类型的索引方法：基于节点序号的索引、基 于节点路径信息的索引和二者相结合的混合索弓l t 6 j ，路径多维索引作为基于节 点路径信息类索引的一种新的方法，由于其摆脱了原有的路径匹配只能基于字 符串匹配的特点，成为研究的热点，本节将重点分析国内外路径多维索引领域 的研究现状。 r u d o l f b a y e r 在1 9 9 7 年首次提出了u b t r e e ( u n i v e r s a lb + t r e e ) ，并将其使 用到多维检索中【7 1 。1 9 9 8 年，r u d o l fb a y e r 和v o l k e rm a r k l 等人提出了用于 u b t r e e 中数据查询的区域查询算法【8 1 ，该区域查询算法采用遍历方式对落在查 询区域的区间节点进行查找，搜索出符合条件的数据点，其对区间的访问是通 过对b + t r e e 的遍历来完成，该算法较为简单，易于实现，但是其查询效率低 下。 针对区域查询存在的效率问题，r u d o l f b a y e r 和v o l k e rm a r k l 等人提出了基 于点与查询区域相交性判断的d r u ( d o w n - r i g h t - u p ) 算法，算法在对b + t r e e 的 节点访问中，通过将当前被访问的叶子节点的右兄弟节点首地址与查询区域进 行相交性判断，减少对树的访问次数，提高查询效率【9 1 。 2 0 0 0 年，f r a n kr a m s a k 和v o l k e rm a r k l 等人提出了将u b t r e e 植入数据库 系统内核【1 0 l 。2 0 0 2 年，t o m a ss k o p a l 和m i c h a lk r a t k y 等人提出了基于区间与 查询区域相交性判断的d r u 算法，该算法在对树进行优化遍历过程中，通过将 2 中山大学硕士学位论文( 2 0 1 0 ) 当前被访问的叶子节点的右兄弟节点所表示的区间与查询区域进行相交性判 断，决定是否对右兄弟节点进行搜索i l 。同年，m i c h a lk r a t k y 和j a r o s l a vp o k o m y 等人提出了使用u b t r e e 方法索引x m l 【l2 1 ，但由于u b t r e e 索引方法还无法很 好的支持x m l 数据的动态变化，因此还处于探索阶段。2 0 0 6 年，t o m a ss k o p a l 等人在基于区间与查询区域相交性判断的d r u 算法的基础上，对区间与查询区 域的相交性判断算法进行改进，采用h y p e r - q u a dt r e e 将区间分解为若干规则的 矩形子区间，通过将每个子区间与查询区域进行相交性判断的方法判断区间是 否与查询区域相交，进一步降低了区域查询的时间花销【1 3 】。 在路径多维索引的数据存储结构方面，r u d o l f b a y e r 和v o l k e rm a r k l 等人提 出的u b t r e e 采用的是检索整个多维空间的方法，节点记录空间分割值，由于 现实世界中数据分布的无规律性，检索空间中容易出现大量的无数据区间，对 查询效率造成影响。2 0 0 3 年，r o b e r tf e n k 提出了b u b t r e e ( b o u n d i n gu n i v e r s a l b + t r e e ) 索引的构想，其在存储树中只保存包含数据点的最小区间，减少了检 索空间中的无数据区间，减低查询时间花销。 1 3 本文的研究内容及意义 1 3 1 目前存在的问题 本文1 2 节对目前国内外学者在路径多维索引领域的研究情况进行了探讨， 从中可以总结出如下不足之处： ( 1 ) 路径多维索引中的区域查询算法虽然对结构树的遍历进行优化，但其 在查询区域包含区间较多且不连续的情况下，仍需访问较多的与查询区域不相 交的区间，导致查询的效率低； ( 2 ) u b t r e e 采用的是存储连续空间区域的方法，由于现实世界里，数据 分布的无规则性，容易造成空间区域中很多区间没有数据，而算法在执行查询 时无法避免对此类z 区间的搜索，而对其进行改进的b u b t r e e ，虽然对无数 据区间的存储上有了改进，但对于实时插入的批量无序数据，其仍生成大量的 子区间，加大i o 切换的开销： ( 3 ) 路径多维索引无法很好的支持储存树中数据的动态变化，其无法对在 动态变化的x m l 文档进行有效的索引。 3 中山大学硕士学位论文( 2 0 1 0 ) 1 3 2 本文的研究目标及意义 针对当前路径多维索引存在的不足之处以及目前在x m l 数据索引中实际 使用的u b t r e e ，本文在t o m a ss k o p a l 于2 0 0 6 年提出的基于数据区间通过 h y p e r - q u a dt r e e 分解为若干规则的矩形子区间的方法进行相交性判断的 u b t r e e 索引算法基础上，对索引树结构进行改进，使用改进的b u b t r e e 方法， 通过建立缓冲，在插入索引树之前对批量数据进行整理排序，使得空间得到有 效的利用，同时对查询区间进行有效的空间分解，减少算法对无关区间的访问， 具体的研究工作如下： ( 1 ) 比较u b t r e e 和b u b t r e e 索引结构，以及改进的b u b t r e e 与原有 索引结构，理论分析它们之间的优缺点； ( 2 ) 建立u b t r e e 以及改进的b u b t r e e 索引模型，实现t o m a ss k o p a l 提 出的基于数据区间分解相交性判断的区域查询算法，对比该算法在u b t r e e 和 在改进的b u b t r e e 上面的查询性能； ( 3 ) 理论分析空间分解方法，结合h y p e r - q u a dt r e e ，对查询区域进行有效 的处理，并且建立相应的算法模型； ( 4 ) 建立基于空间分解的改进b u b t r e e 索引模型，对比基于空间分解的 区域查询算法和原有区域查询算法在改进b u b t r e e 索引树上的查询性能。 1 4 论文的组织结构 第一章：绪论，对提出问题的背景和现实意义进行阐述，同时对该领域的 研究现状进行归纳和总结，提出了本论文的研究思路。 第二章：路径多维索引研究基础及问题描述，简要介绍了路径多维索引的 相关概念，对当前路径多维索引中数据存储结构和区域查询方面存在的问题进 行描述。 第三章：空间分解及改进b u b t r e e 索引方法描述，针对上一章所描述的 当前路径多维索引存在的问题，提出了改进的b u b t r e e 以及空间分解方法， 并且对这两个方法进行详细介绍分析。 第四章：基于空间分解的改进b u b t r e e 索引模型，建立新的路径多维索 引模型：采用改进的b u b t r e e 方法对批量数据进行插入处理，同时在查询过 4 中山大学硕士学位论文( 2 0 1 0 ) 程中采用空间分解算法对查询区域进行有效分解，并在索引模型理论基础上， 编程实现该索引模型，比较在相同的数据条件下查询算法在原有的u b t r e e 和 改进b u b t r e e 上执行相同查询所花的时间，以及在改进的b u b t r e e 上，原有 的区域查询算法和基于空间分解的查询算法执行相同查询所使用的时间。 第五章：研究总结与展望，对本论文的研究情况进行总结，突出创新点和 研究意义，并总结不足之处，对下一步的研究工作进行展望。 1 5 本章小结 本章首先简要介绍了x m l 及其特点，接着描述了基于x m l 数据的查询和 查询存在的缺陷，研究人员针对x m l 查询存在的缺陷提出的多种不同类型的 x m l 索引，分析了节点记录类型索引的研究现状并且着重介绍了路径多维索引 的研究发展现状，分析该领域存在的缺陷，进而提出了本论文研究的目标和意 义，最后对本文内容的结构安排进行了说明。 中山大学硕+ 学位论文( 2 0 1 0 ) 第二章路径多维索引研究基础及问题描述 2 1 路径多维索引相关概念介绍 路径多维索引是一种将查询路径转换为多维空间点，进而对数据集进行多 维管理的索引方法，其基本思想是借助空间填充凸线将多维空间的数据转换为 线性维的数据，并且借助b + t r e e 树结构对线性维的数据建立索引。 2 1 1 空间填充曲线 空间填充曲线是一种分形曲线。从整体上看，分形曲线的几何图形是处处 不规则的，但在不同尺度上图形的规则性又是相同的，其局部形状又和整体形 态相似，它们从整体到局部都是自相似的。空间填充曲线的构造过程是依次填 充曲线的过程【14 1 。 空间填充曲线的创始人是意大利数学家p e a n o ，其为了验证g e o r gc a n t o r 有违直觉的结论：单位区间内的无限数量点和有限维流形的单位空间内的无限 数量点具有相同的基数，即如何用一维曲线填充多维空间，提出了空间填充曲 线，其形状如图2 - 1 所示【1 5 1 ： 图2 - 1 1 5 】p e a n o 空间填充曲线示例图 随着应用的发展，空间填充曲线又延伸出几种形式，其中具有代表性的有 以下三种： 6 中山大学硕士学位论文( 2 0 1 0 ) ( 1 ) h i l b e r t 曲线( 希尔伯特曲线) ：一种能填充满一个平面正方形的分形 曲线( 空间填充曲线) ，由大卫希尔伯特在1 8 9 1 年提出。由于它能填满平面， 它的豪斯多夫维是2 ，取它填充的正方形的边长为1 ，第n 步的希尔伯特曲线的 长度是2 n 一2 一 1 6 1 ，其形状如图2 2 所示： 图2 2 【1 6 1h i l b e r t 曲线实例图 ( 2 ) z 曲线：由g m m o r t o n 于1 9 6 6 年在p e a n o 曲线的基础上提出的 种新的空间填充曲线。z 曲线由于其良好的保序性而经常在计算机领域中得到 使用，主要应用在将多维空间的数据映射到一维的数据结构中【1 7 1 。z 曲线由于 其曲线形状为z 形，故命名为z 曲线，图2 3 为z 一曲线实例图： 了俨 z 厶 弓屠。b 哆 二荔利乏事 图2 - 3 1 7 】厶曲线实例图 ( 3 ) c 曲线：分别由意大利科学家e r n e s t oc e s h r o 和g f a r b e r 于1 9 0 6 年 和1 9 1 0 年相继提出的一种自相似的的分形空间填充曲线，其曲线图如图2 4 所 7 中山大学硕士学位论文( 2 0 1 0 ) - - 爪： 图2 4 【1 7 1c 曲线实f 勇1 匿t 以上三种是具有代表性的空间填充曲线，其中h i l b e r t 曲线的数据聚类特性 最佳，但其映射过程复杂，g r a y 曲线虽然构造简单，但是其数据聚类特性较差， 而z 曲线虽然在数据聚类特性上不及h i l b e r t 曲线，但其映射简便，且映射后数 据保持良好的偏序关系，故在计算机领域中得到广泛应用，因此本文所研究的 路径多维索引使用z 曲线作为空间填充曲线。 2 1 2 乙曲线及其空间映射相关概念介绍 ( 一) z 一地址 空间填充曲线的目的是将多维空间中的点映射到一维空间中，且在映射过程 中必须保持数据之间的偏序关系，因此在映射过程中，算法需要将空间中的坐标 点转换为唯一确定的值，该值称为空间曲线地址，由于本文的路径多维索引采用 z 一曲线，故称之为z 一地址。 将z 曲线定义为n 维空间o n 与一维空间l 之间的一一映射，记做z ：o “一l ，若 点a o n ，$ 1 j z ( a ) el ，称z ( a ) 为点a 的z 值。 对于n 维空间o “中的任一点a ，假设其点坐标为( a l ，a 2 ，a 。) ，每一维上的坐标 值a 都可以用二进制数值表示为：a i = a 争l a ，蛆a ，o ，则点a 的z 一地址可以表 示为【”1 ： s - i z ( a ) = 4 ，2 州。1 ( 2 1 ) 8 中山大学硕士学位论文( 2 0 1 0 ) 利用z 地址的构造方法，可咀将n 维审问与一维宅m 建立映射关系，并目根 拈z 地址值山小到大的顺序将空川l p z 地址值相邻的两点片j 直线连接，贯穿整 个空的| f l 线则称之z 曲线，图2 - 5 ( a ) 是基数为8 的二维空【l j 中z 一地址的分确j 圈， 幽2 - 5 ( b ) 是在图2 5 ( a ) 基础上，将空白j 坐标点按空间地址山小到大链接的曲线圈： 图2 - 5 ( a ) 空闻地址分布示怖图图2 - 5 ( b ) 1 9 1z 曲线空间填充示例囤 ( 二) z - 区间 z 区问是以z 一曲线为卒间填充曲线的多维卒间中一段连续的z 曲线段所覆 盖的空6 j 区域。假设有最小z 地址为a ，最大z 地址为b 的连续z - 曲线段该z 一 曲线段所覆盖的z 一区问则可表示为h b 】，其中a ，b 又可分别称为该z 区间的起始 和终止值。图2 6 为二维空唰的z 一区阳j 示例图，图中所示的：维空间被分割为6 个 z 区间： o ，3 】， 4 , 9 ， 1 0 ，3 1 】， 3 2 ，3 5 ， 3 6 ，4 7 ， 4 8 ，6 3 ，相z 乓b 区间分别用不 同颜色表示： 图2 _ 6 【2 0 lz 区间示例图 中山大学硕士学位论文( 2 0 l o ) 2 1 3 查询区域介绍 多维路径索引在执行查询操作时将查询语句映射到多维空间中的一个子空 间中，该子空间称为查询区域，可通过一系列的坐标区间集来表示。假设有维基 数为c 的n 维空间o ，查询区域在第i 维上的坐标区间是【m 岫，m a x i 】( 其中m i l l i 和 m a x i 均为o n e 1 的整数且m i n i 不大于m a x i ) ，则该查询区域可以表示为： m i n i ， m a x l ，【m 近，m a x 2 ，【m i n ，m a x ) ，图2 7 为二维空间的查询区域示例图，图 中深灰色的矩形区域为一个查询区域，该查询区域里面包含了四条z 曲线段i i ， 1 2 ，1 3 ，1 4 ，假设纵坐标为第一维，横坐标为第二维，维基数从0 开始，则该查询 区域为 【2 ，4 】，【2 ，5 】。 歹厂专l 厂切 l 巾 么 乡! 月 守 冽 ( 罗 i 蒯 乃 叠 7 i 么。 一。t 一 卜 w 一” 一一一 7尸7 k厂7 b7 i 么 彳 o ， “，_ f l 一 蒯 。 彳 1 7 y 一7 i 么。厶ju么 l 图2 7 【2 1 】查询区域示例图 2 2 路径多维索引数据储存方法介绍 路径多维索引由于借助b + t r e e 对数据进行检索，其数据点的插入删除通过 对b + t r e e 的操作来完成。 采用u n i v e r s a lb + t r e e 索引方法对数据进行索引时，由于其对整个多维空间 进行检索，每个节点保存一个z 区间，不同z 区间之间互不相交，且节点的子节 点按照其存储的z 区间或z 地址由小到大从左向右排列，当由数据变动引起的树 节点分裂时，需要计算该节点所表示的z 一区间的分割值，即需要重新计算新生成 的树节点的z 区间范围。 z 区间分割值计算的原则是产生的分割值在满足b + t r e e 节点分裂基本条件 的情况下应该尽量使得分割后的两个区间有较规则的形状。当前计算z 区间分割 l o 中山大学硕士学位论文( 2 0 1 0 ) 值的算法基本思想是通过z 地址的二进制形式判断其在空间中所处的位置，从而 判断分割后新生成的z 区间的形状。根据采用z 曲线作为填充曲线的多维空间中 z 地址的分布特点，可知二进制形式的z 地址从最低位开始，具有连续的l 的个 数越多，则其形状越规则。 假设有一棵n 阶的b + 一t r e e ，树中有一节点n o d e ( n o d e 为非根节点) ，其保存的 z 一区间为h b 】，由于插入第n + 1 个子节点，需要将其分裂为两节点，则z 区间分 割值算法可描述如下： ( 1 ) 获取节点n o d e 的第n 2 个子节点所存储的z 一区间h ，b i 】的最大值b i 和第 n 2 + 1 个子节点所存储的z 一区间 a 0 ，b j 的最d 、值a j ，分别将它们的值赋给变量s p m i n 和s p m a x ( 若节点n o d e 的子节点为叶子节点，贝u s p m i n 和s p m a x 分别取值于节点 n o d e 的第n 2 个子节点和第n 2 + 1 个子节点所存储的z 地址) ； ( 2 ) 将整数s p m i n 和s p m a x 分别转化为二进制形式s t r s p m i n 和s t r _ s p m a x ； ( 3 ) 从字符串的第一位开始，比较字符串s t rs p m i n 和s t rs p m a x ，获取它们 之间的第一个字符不同的位，将其值赋给变量i p l a c e ； ( 4 ) 若i p l a c e 为字符s t r s p m a x l 拘最后一位，则返回s t r _ s p m i l l 的整数形式， 算法结束；否则将字符串s t rs p m a x 中第i p l a c e 位后的所有位均置为o ； ( 5 ) 将字符s t r _ s p m a x 转化为整数形式，并赋值给变量s p v a l ，若s p v a l 的 值为0 ，则返回0 ，算法结束；否则返回s p v a m ，算法结束。 图2 8 为4 阶b + t r e e 节点分裂示例图，左边树的根节点由于插入新的子节 点，需对根节点进行分裂操作，根据上述分割值算法，可知整数区间【9 ，2 3 中的 任意整数均可作为分裂值，通过算法计算可得：取1 5 为z 一区间分割值可使得分割 后的两个子区f 日q o ，1 5 和 1 6 ，6 3 具有最规则的形状。 同 目回固回e 图2 - 84 阶b + t r e e 节点分裂示例图 中山大学硕士学位论文( 2 0 1 0 1 2 3 路径多维索引区域查询算法研究综述 区域查询算法是路径多维索引的核心算法，其作用是通过对索引树的遍历， 搜索出所有落在查询区域内的数据点。区域查询算法从提出到现在经历了多次改 进，其算法效率也得到极大的提高，本小节将简要介绍分析区域查询算法的几个 具体实现方法。 2 3 1 b - m 算法 区域查询算法最早t h b a y e r 和m a r k l 提出，称为b - m 算法，可简要描述如下： ( 1 ) 计算查询区域起点的z - 地址值，对索引树进行遍历，查询存储的z - 区间 包含该二地址的叶子节点，并将该z 一区间设置为活动z - 区间； ( 2 ) 在活动z - 区间中搜索所有落在查询区域的数据点： ( 3 ) 将z 一地址值加上设定的步长，判断递增后的z 一地址是否在查询区域内， 若在，则遍历索引树，定位到存储的z - 区间包含该z - 地址的叶子节点。将该叶 子节点说存储的z _ 区问设置为活动z _ 区间，返回步骤二：若不在，则判断该z _ 地址值是否大于查询区域终点的z _ 地址，若小于，则算法继续执行第三步，否 则算法结柬。 图2 9 为b - m 算法在二维空问中的执行示例圈： 囊dh 卜 掣一l ! 棵 m 2 - s r l i & m 算祛执行示倒田 1 2 中山大学硕士学位论文( 2 0 1 0 ) b m 算法在获取下一个落在查询区域内的z 一地址时，采用的是z 一地址值逐 步递加的方法，该方法在查询区域与z 一区间相交的数量较多的情况下存在以下不 足之处： ( 1 ) 由于在当前落在查询区域的z 一地址和下一个落在查询区域的z 一地址之 间可能存在大量落在查询区域外的z 一地址，因此算法的性能很不稳定； ( 2 ) 算法每次定位到对应的叶子节点时都需要对索引树进行遍历，增加了 i o 切换开销。 2 3 2b m d r u 算法 针对b m 算法存在的不足，b a y e r 和m a r k l 提出算法d r u ( d o w n 砌g h t u p ) t 1 1 1 ， 简称b md r u 算法。该算法对索引树的遍历进行优化，并且使用缓存保存访问 过的路径节点，算法步骤描述如下： ( 1 ) 计算查询区域起点的z 一地址值，对索引树进行遍历，查询存储的z 一区 间包含该z 一地址的叶子节点，栈保存访问路径节点，并将该z 一区间设置为活动 z 一区间； ( 2 ) 在活动z 一区间中搜索所有落在查询区域的数据点； ( 3 ) 判断当前被访问的节点的右兄弟节点的区间起始地址是否在查询区域 内，若相交则将该右兄弟节点存储的z 一区间设置为活动z _ 区间，同时栈保存该 右兄弟节点，返回步骤二，否则判断该右兄弟节点所存储的z 一区间起始地址是 否大于查询区域的终点的z 一地址，若是，则算法结束，否则返回该节点的父节 点，栈顶元素出栈，若栈为空，则算法结束，否则循环执行步骤三。 b md r u 算法减少了对索引树的遍历次数，该算法以z 一区间的起始地址是 否落在查询区域来判断该z 一区间是否和查询区域相交，判断方法的时间复杂度 为常熟级别，但由于z 一区间的形状无规则，该相交判断方法无法对区间起始地址 不在查询区域内但其覆盖的区域与查询区域相交的z 一区间进行访问。 2 3 3t d r u 算法 为了进一步对区域查询算法进行改进，t o m a ss k o p a l 等人提出了基于区间分 解的z 一区间与查询区域相交判断的d r u 算法i 坦】( 简称t d r u 算法) 。该算法采 中山大学硕士学位论文( 2 0 l o ) 用区间分解的算法，有效的解决了无规则形状的z 一区间与查询区域的相交性判 断问题。 t d r u 算法与b m _ d r u 算法的区别在于对z 一区间与查询区域的相交性判 断上采用不同的方法，t d r u 算法采用区间分解的方法，将z 区间分解为尽量少 的规则形状区间，避免了b md r u 算法所采用的以z 区间的起始地址是否落在 查询区域来判断该z 一区间是否和查询区域相交的方法所带来的缺陷。 t d r u 算法中的z 区间分解算法基本思想是借助z 区间起始和终止地址的 二进制形式字符串判断该区间的形状，进而将其分解为若干规则形状的子区间， 通过对子区间的判断确定z 区间是否与查询区域相交，解决了由于z 区间的形状 无规则所带来的与查询区域相交性判断困难的问题。 2 4 路径多维索引及其问题描述 路径多维索引主要由两部分组成：数据索引树和数据查询算法，路径多维 索引通过空间填充曲线和索引树将多维空间点映射到线性空间并进行索引管理。 数据的查询通过查询算法将查询语句映射到空间区域，并调用区域查询算法对查 询区域进行数据搜索，因此索引树的数据存储结构和区域查询算法决定了索引的 性能。 当前实现路径多维索引的u b t r e e ( u n i v e r s a lb + t r e e ) 方法主要存在以下 缺陷： ( 1 ) 在数据存储结构方面：由于u b t r e e 对整个多维空间进行检索，但数 据分布无规律，容易出现数据集中在某个区域，在这种情况下，索引树中节点保 存了大量的无数据区间，查询算法对此类节点的遍历将严重影响查询效率； ( 2 ) 区域查询方面：虽然当前有许多改进的区域查询算法，但是它们大都 对树的遍历方面进行改进，当被查询区域不完全覆盖的z 区间越多时，算法需要 访问的树节点越多，算法的效率也随之降低。 2 5 本章小结 本章介绍了路径多维索引及其相关概念，重点介绍和分析了路径多维索引 中的数据存储方式以及数据查询算法中的区域查询算法的研究进展。最后总结 1 4 中山大学硕士学位论文( 2 0 1 0 1 当前实现路径多维索引的u b t r e e 方法在索引数据存储方式和区域查询算法方 面存在的问题和缺陷。 1 5 中山大学硕士学位论文( 2 0 l o ) 第三章基于空间分解的改进b u b t r e e 索引模型 3 1 基于空间分解的改进b u b t r e e 索引介绍 基于空间分解的改进b u b t r e e 索引方法是一种针对上一章所总结的当前 u b t r e e 索引方法存在的缺陷提出的改进路径多维索引方法。当前基于空间分 解的改进b u b t r e e 索引方法主要分为两部分： ( 1 ) 采用改进的b u b t r e e 索引树对数据建立索引，减少索引树对无数据 区间的存储； ( 2 ) 采用空间分解方法，对查询区域进行有效的分解，将其分解为最少条 数的连续z 曲线段，同时缓存存储z 曲线段的叶子节点，减少对索引树的遍历 次数。 基于空间分解的改进b u b t r e e 算法通过以上两个方面的改进，提高了路 径多维索引对数据的查询效率。下面的小节将分为两部分对改进算法进行详细 介绍分析。 3 2 基于b u b t r e e 改进数据存储算法 当前造成u b t r e e 索引树中存储了大量无数据区间的原因是其对整个多维 空间进行检索，若索引树中同级的所有节点按其所保存的z 区间的顺序拼接， 这些区间将构成整个多维空间。 b u b t r e e 索引方法针对u b t r e e 的这个缺陷，对索引树中的数据存储结构 进行改进，采用存储有数据的区间段方法代替原有的区间分割方法，该方法有 效的减少了索引树对无数据区间的存储，但该方法在插入的数据量大时，产生 的区间节点多，仍然影响了查询算法的性能。 改进的b u b t r e e 索引树是一种基于b u b t r e e 所采用的存储区间段方法的 改进索引树，其基本思想是通过对数据建立缓存，排序，组合生成叶子节点， 1 6 中山大学硕士学位论文( 2 0 1 0 ) 自下而上生成索引树，减少了由数据点插入引起的区间节点频繁分裂，同时对 节点数据结构进行改进：在数据结构中加入指向父节点的指针域，使得查询算 法在对索引树进行遍历时，减少对树节点的访问次数。 针对插入的数据量不同，改进的b u b t r e e 索引建树过程主要有两个算法 支持：批量数据建树算法和单数据插入算法，下面的小节将对这两个算法进行 理论上的分析介绍。 3 2 1 批量数据建树算法 批量数据建树算法的基本思想是通过对无序数据的重新整理排序，使得数 据集按照z 地址值由小到大有序，并根据设定的区间的数据容量，依次从有序 数据中读取若干数据点，使用b u b t r e e 索引树的节点数据结构建立对应的数 据节点，同时