（计算机应用技术专业论文）通用r树的设计与实现.pdf

江 苏 大 学硕 士 学位论 文 摘要 对象关系型数据库管理系统( o r d b m s ) 是面向对象技术与数据库技术的结合走向 成熟的产物。它提供对复杂数据进行复杂查询的支持，从而能够更好的满足多媒体、w e b 应用以及一些新的商业领域应用的需求。o r d b m s 提供了用户自定义新数据类型( u d t ) 和函数的功能，而数据类型的扩展性必然需要与之配套的具有扩展性的索引机制，用于对 u d t 数据的访问。 由于信息数据的高维性、复杂性和海量性，传统的索引方法已不能满足用户的查询需 求；遇到某些复杂的用户自定义数据类型，传统方法甚至无法处理。索引方法的局限性很 大程度上影响了数据库系统的查询效率。因此，开发一种高效的、能够对任意类型的索引 关键字进行查询的索引方法是o r d b m s 发展的必然要求。本文设计了一种可用于关系以 及多维空间数据库管理系统的通用r 树索引技术g r t 。该查询树解决了传统r 树只能对坐 标类型数据进行检索的问题，实现了索引关键字类型的通用性。g r t 不仅具有传统r 树的 基本功能，还为用户设计了一套关键字方法，用户可以根据实际系统的需要来自主定义具 体的查询操作方式。g r t 的优越性主要表现在能对任何用户自定义数据类型及抽象数据类 型进行索引，使查询更具灵活性和广泛性。 本文的主要贡献如下： 1 ) 分析了r 树索引的优越性和局限性，针对r 树无法对用户自定义数据类型进行索 引的缺陷，结合g i s t 方法，提出一种通用r 树的索引机制g i 玎方法，以实现索引关 键字的通用性。 2 ) 对提出的通用索引方法g r t 进行通用性分析，从其结构上和查询树方法的执行过 程出发，证明其可以有效的实现索引关键字类型和维数的通用性。并结合实例，说明了g r t 方法的扩展性。 3 ) 根据p o s t g r e s q l 数据库的特点，在该开发平台上设计并实现了g r t 模块。并结合实验 测试结果，从实践上证明了g r t 方法的通用性和高效性。 关键词：r 树，g r t 方法，索引关键字的通用性，索引的扩展性 江苏大 学 硕士 学 位论文 a b s tr a c t o b j e c t r e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e m ( o r d b m s ) i sam a t u r ep r o d u c tw h i c ho n t h eb a s i so fc o m b i n a t i o no ft h eo b j e c t o r i e n t e dm a n g e m e n ts y s t e ma n dd a t a b a s et e c h n o l o g y i t s u p p o r t sc o m p l e xq u e r i e st oc o m p l e xd a t a ，s oi tc a nd ob e t t e rw h e nd o i n gq u e r yt om u l t i - m e d i a , w 曲a p p l i c a t i o n ，a sw e l l a ss o m en e wa r e a so fb u s i n e s sa p p l i c a t i o n s o r d m sp r o v i d e s c o n v e n i e n tf u n c t i o n a l i t yt ou s e r st oa l l o wt h e md e f i n i n gn e wd a t at y p e ( c a l l e du s e r - d e f i n e d d a t a t y p e ，u d t ) a n ds u p p o r tf u n c t i o n s t h ee x t e n s i o no fd a t at y p ew i l li n e v i t a b l yr e q u i r ea n e x t e n s i b l ei n d e x i n gm e c h a n i s mt os u p p o r tu d t s d u et oc u r r e n td a t a sh a v es o m ef e a t u r et h a td i f f e r e n tf r o mt r a d i t i o n a ld a t at y p e s 1 i k eh i g h l y d i m e n s i o n s ，c o m p l e xs t r u c t u r e sa n dl a r e g eq u a n t i t y s o ，t r a d i t i o n a li n d e x i n gm e t h o dc a nn o t m e e tt h en e e do fu s e r s q u e r i e s f o rs o m ep a r t i c u l a ru d t s ，t r a d i t i o n a li n d e x e se v e nc a nn o t h a n d l e o b v i o u s l y , t h el i m i t a t i o n so ft h e s ei n d e x e sa f f e c tt h ee 伍c i e n c yo fd a t a b a s es y s t e m a sa r e s u l t ，t od e v e l o pah i g h l ye f f i c i e n ti n d e xw h i c hc o u l dr e t r i e v ea n yt y p eo fk e y w o r di sac e r t a i n r e q u i r e m e n to fo r d b m s t h i sp a p e rp r o p o s e san e wm e t h o dc a l l e dg i 盯( g e n e r a l i z e dr t r e e ) w h i c hc a nb e u s e di nr e l a t i o n a la n dm u l t i d i m e n s i o n a ld a t a b a s em a n a g e m e n ts y s t e m t h i s m e t h o dm a i n l ys o l v e st h ep r o b l e mt h a tt h et r a d i t i o n a lrt r e ec a l lo n l yi n d e xd a t a sw i t h c o o r d i n a t et y p e i ta c h i e v e st h ee x t e n s i b i l i t yo fi n d e x e dk e yt y p e s e x c e p tc o m m o nt r e ef u n c t i o n s ， g r tl e a v e su s e r sas e to fk e ym e t h o d s ，w h i c hd e f i n e db yu s e r sa c c o r d i n gt ot h er e q u i r e m e n to f s o m ep h y s i c a ls y s t e m t h ea d v a n t a g eo ft h i si n d e xi st h a t ：i tc o u l db eu s e dt oi n d e xt h ea b s t r a c t d a t at y p e sw h i c hd e f i n e db yu s e r s ，m a k i n gr e t r i e v e p r o c e s s i n gm o r ef l e x i b l e a n dm o r e e x t e n s i b l e t h ea u t h o r sm a i nw o r k sa r el i s t e da sf o l l o w s ： ( 1 ) a n a l y z et h ea d v a n t a g ea n dl i m i t a t i o no ft r a d i t i o n a lr t r e es t r u c t u r e i na c c o r d a n c ew i t h r t r e e sd e f e c tt h a ti td o e s n ts u p p o r tu d t a n dc o m b i n e dt h ee x t e n s i b i l i t yo fg i s t , w e d e s i g nan e wg e n e r a l i z e dr - t r e ei n d e x i n gm e c h i n i s m - - g r t t h i sm e t h o di su s e dt or e t r i e v e u s e r - d e f i n e dd a t at y p e s ( 2 1f r o mt w os i d e st oi l l u s t r a t et h eg e n e r a l i t yo fg r tm e t h o d ：t h es t r u c t u r ec h a r a c t e ra n dt h e p r o c e s so ft r e ea l g o r i t h m s t h e yp r o v et h a tt h eg r t c a na c h i e v et h eg e n e r a l i t yo fd a t at y p e a n dt h ed i m e n s i o no fi n d e x e dk e y se f f i c i e n t l y w ea l s op r o v i d ee x a m p l e st os h o wt h e e x t e n s i b i l i t yo fg r t ( 3 ) a c c o r d i n gt ot h ef e a t u r e so fp o s t g r e s q ld a t a b a s e ，w ed e s i g na n dd e v e l o pg r to nt h i s e x t e n s i b l ep l a t f o r m c o m b i n e dw i t ht h ee x p e r i m e n t a lr e s u l t s w ep r o v et h a tg i 盯m e t h o dh a s h i g h l ye x t e n s i b i l i t ya n de f f i c i e n c y k e yw o r d s ：r - t r e e ，g r tm e t h o d ，g e n e r a l i t yo fi n d e x e dk e y , e x t e n s i b i l i t yo f i n d e x 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，同意学校保留并向国家有关部门或机构送交论文的 复印件和电子版，允许论文被查阅和借阅。本人授权江苏大 学可以将本学位论文的全部内容或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密一。 学位论文作者签名：李毙 指导教师签名： 釉也， 2 0 0 9 年歹月2 日2 0 0 9 年多月日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的 指导下，独立进行研究工作所取得的成果。除文中已注明引 用的内容以外，本论文不包含任何其他个人或集体已经发表 或撰写过的作品成果。对本文的研究做出重要贡献的个人和 集体，均已在文中以明确方式标明。本人完全意识到本声明 的法律结果由本人承担。 学位论文作者签名：峦磊 日期：】口口7 年占月 江 苏大 学 硕 士 学 位论文 第一章绪论 1 1 研究背景及目标 数据库技术产生于2 0 世纪6 0 年代后期，当时计算机开始广泛的应用于数据管理，对 数据的共享也提出了越来越高的要求。传统的文件系统已经不能满足人们的需要。在近5 0 年的发展过程中，数据库技术经历了由非关系型数据库到关系型数据库的转变。同时，数 据库管理系统( d b m s ) 也应运而生，这类软件用于对数据库进行管理控制。其管理和控 制功能包括：数据的定义、数据存取和修改、数据库的运行管理、数据库的建立和维护等。 除此以外，还要求数据库管理系统能够及时准确的满足多个用户的并发存取操作，另外还 要保证事物的原子性、数据的一致性、可并发操作及发生系统故障时的可恢复性i l j 。近年 来，由于地理信息系统( 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 ， g i s ) 技术的快速发展，空间数 据库也随之发展起来，对d b m s 提出了很多新的更高的要求，传统的d b m s 亟需改进。 空间数据库【2 】是描述、存储和处理空间数据及其属性数据的数据库系统。与传统数据 库相比，空间数据库管理系统涉及对大量多维空间实体的存储与操作。这些空间实体1 3 j ( 1 ) 往往具有不规则的几何形状，且实体之间的空间关系复杂( 相交、相邻、包含等拓扑关系) ， 通常不太可能用一个关系表，以定长元组存储这类对象的集合；( 2 ) 难以定义合理的空间 目标的空间次序，无法应用传统数据库中使用的排序技术。( 3 ) 空间运算符的不闭合性。 除此以外，还有计算代价昂贵等因素，使得大部分现有的数据库管理系统无法管理空间数 据，或在管理空间数据的时候效率较低。例如关系模型能够较好的处理拓扑关系，但对横 跨空间区域的复杂层次关系的表示则无能为力；而面向对象模型能够处理拓扑和层次关 系，但却难以处理空间中重要的连续性现象。为了有效提高对空间数据的处理效率，尤其 是针对空间位置的实时查询效率，空间数据库必须利用有效的索引机制。 索引是用于提供快速的、有选择性的存取数据库的一种机制，它相当于一个映射机构， 将属性的值转换为相应记录的地址或地址集。一个数据库系统需要一套索引机制帮助它根 据数据的空间定位迅速的检索数据项目。早在关系数据库系统中，b t r e e 的成功应用就让 我们认识到索引技术的重要性。在空间数据库中，空间数据索引作为一种辅助性的空间数 据结构，介于空间操作算法和地理对象之间，它通过筛选，排除大量与特定空间操作无关 的地理对象，从而缩小了空间数据的操作范围，提高了空间操作的速度和效率。 当前使用的空间数据库索引方法主要是以树结构为基础，其中r 树【4 】更是占据着极其 江 苏大学 硕士 学 位论文 重要的位置，是当前使用最多一种多维对象索引结构。r 树及其变体，以及很多以r 树为 基础的改进方法，是当前检索空间数据的主要方法。它也是p o s t g r e s 、o r a c l e 等重要数据 库的内建索引方法。 r 树是2 0 世纪8 0 年代由g u t t m a n 等人提出的一种高度平衡树，其实质是b t r e e 在k 维空间的自然扩展。r 树的思想是将空间目标及索引空间用其最小外包矩形来近似表示， 可以简化计算、减少存储空间；将空间上邻近的目标组织在同一结点或同一分支，可以减 少外存访问次数。r t r e e 的叶结点上的索引记录形式是 ，其中o i d 为空间对象 在磁盘页面上的记录标识符，卜( i o ，i l ，i k 1 ) 为对应空间对象的在k 维空间中的最小 边界矩形，i i 是一个封闭边界【a ，b 】，描述了对象在第i 维方向的范围；r 树中间结点记录的 形式为 ，p 为指向子树根结点的指针，i 为包围其子树根结点中所有目录矩形或数据 矩形的最小边界矩形，并不存储实际数据。树的每个结点对应一个磁盘页面。 在r 树中，既可以实现空间点查询，也可以实现空间范围查询，都采用自项向下递归 的方法处理。查询点( 或区域) 首先同根结点中的每个记录项 进行比较。如果查询 点在i 中( 或查询区域与其交叠) ，则查找算法就递归地应用在p 指针指向的r 树结点上。 该过程直到r 树的叶结点层为止。最后再将叶结点对应的数据项取出，与查询点( 区域) 做进一步的精确性检查。r 树的最大j 擞k l o g m n j 1 ，其中n 是树中项的总数。r 树检索 的最好情况是0 ( 1 0 9 m n ) ，最坏情况是o ( n ) ，即成为线性查找。 目前，r t r e e 是空间数据索引方法中最重要的一种层次索引方法。其优越性在于：可 以自动平衡、空间利用率较高、适合于外存存储；且它是一种完全动态的空间索引数据结 构，插入、删除、查询可以同时进行，且不需要定期重组；具有较强的灵活性和可调节性， 建树过程中无需预知整个空间对象所在的空间范围，同时它还具有较高的执行效率。但r 树也存在许多问题，主要包括：由于中间结点目录矩形允许发生重叠，造成多条查找路径 的存在，而其中的某些查找路径往往不包含查找结果，这就影响了查找性能。此外，它只 能对空间对象进行查询，这就大大限制了该方法的应用范围。由于其结构上的局限性，r 树对于用户白定义数据类型的查询通常也不能得到有效执行，且只能在一个字段上建立索 引，不能同时对多个字段检索。 在r 树之后，又提出了r 宰树【5 】、r + 树1 6 】等改进的索引结构。这两种树结构都致力于 减少中间结点的覆盖和重叠，提高检索效率。后来又出现很多索引技术采用多种结构、多 种策略来提高效率，如x 树1 7 l 综合了线性组织结构与r 树层次组织结构，还提出了超结点 ( s u p e m o d e ) 的概念。对于中间结点中索引空间重叠无法避免的一部分数据，采取线性的 2 江苏大 学 硕士 学 位论文 组织方式，存于超结点中；对于其他数据，依然组织在形式如r 树的层次结构中。这样就 避免了索引空间的重叠率，提高了对高维空间大数据量的索引效率。但是这些索引方法都 是单纯在树的结构上做修正，对查询树所能检索的数据类型却没有加以关注。因此，这些 方法和r 树一样，仍然只能对空间数据类型进行检索，造成空间数据类型的查询和传统数 据类型以及用户自定义数据类型查询的分离，不能实现统一的检索。且它们也都不能处理 多字段的联合查询问题。 随着数据库所存储的数据量的不断增大，数据记录复杂性的不断提高，必须找到一种 通用的索引结构，可以对任何数据类型进行统一的检索。 近年来，o r d b m s 的发展变得越来越商业化，过去研究的数据类型已经明显不能满 足应用需求。但是对象关系型数据库管理系统的一个关键优点就在于它可以使用用户自定 义的数据类型。在很多高级应用中，这都是一个非常重要的特性，因为许多非标准域模型 都需要使用用户自定义类型【8 】。我们从面向对象模型的发展趋势上可以作出推断：用户自 定义类型将会得到越来越广泛的应用。与此同时产生的一个问题就是，其查询的便利性需 要得到提高。在空间数据库系统中除了空间数据和传统数据类型，也存储了一些用户自定 义的数据类型。系统中的空间信息与固有属性信息一般采用分离组织存储的方式，以增强 整个系统数据处理的灵活性，尽可能减少不必要的时间与空间的开销。而现有的空间索引 技术对于空间属性和固有信息属性的联合查询也都是采用两种索引联合的方式进行两次 检索。对于类似于“找出江苏省内的所有人口超过1 0 万的县( 市) 的查询，一般都会通 过两个子查询进行：一个二维的空间查询和一个一维线性查询。因为传统的空间索引只能 对空间属性进行查询，对于“人口超过1 0 万的县( 市) 这样的查询，空间索引无能为力。 因此当非空间属性在查询中占的比例很大时，空间索引的效率明显低下。而对于更为复杂 的用户自定义数据类型，传统索引有时甚至无法对其进行检索。为了能对任意类型的属性 联合实现一次检索，也就是实现索引关键字的通用性，本文提出了一种可用于关系及多维 空间数据库管理系统的通用r 树索引技术，以改进原有的多维索引机制。 1 2 研究内容 本课题的目的是创建一个以p o s t g r e s q l 为平台的扩展r 树索引结构，解决传统r 树 只能对空间坐标类型数据进行检索的问题，实现索引关键字的通用性。同时，采用堆更新 技术，改进传统r 树的每次更新都要从根到叶结点进行的缺点，提高查询树的效率。主要 研究内容包括： ( 1 ) 对关键字进行研究，包括传统索引关键字类型的局限性研究；传统索引方法的局 3 江 苏 大 学 硕 士 学 位论文 限性；用户自定义数据类型的出现对索引提出的新要求；以及通用的索引应具备的功能等 盘譬 写于o ( 2 ) 结合空间索引技术发展的方向，以g i s t 结构为基础，提出一种改进的索引方法 g r t ( g e n e r a l i z e drt r e e ) 。对该索引方法的原理、及相应的并发控制和恢复机制进行详细 介绍。并对g r t 方法如何实现通用性进行了分析，并提出了一些提高该索引方法的查询效 率的方式。g r t 的通用性包括两个方面：支持多字段索引以及对用户自定义基类的查询。 ( 3 ) 以p o s t g r e s q l 为平台，实现g r t 索引机制。通过试验的方法，利用g r t 完成 不同类型属性联合的查询。同时，对g r t 机制的存储利用率和查询效率进行测试和性能分 析。 1 3 文章结构 本文以p o s t g r e s q l 为应用平台，g i s t 索引结构为基础，讨论了空问数据库的索引技 术的发展方向。第一章介绍了以r 树为代表的空间索引的优点及局限性、本课题的研究意 义和目标。第二章对高维实体的属性及属性之问的关系进行研究，探讨了如何针对属性建 立索引的问题，同时提出一些从属性出发提高索引效率的方法。第三章对提出的g r t 理论 进行介绍，包括该查询树的结构、对应的查询算法以及并发控制及恢复机制等。第四章在 介绍p o s t g r e s q l ，并在该数据库中实现g r t 。第五章使用几个具有代表性的应用实例g r t 索引方法进行性能测试。第六章对全文所作的工作进行了总结和展望。 4 江苏大 学 硕 士 学 位论文 第二章索引关键字属性的研究 从数据库中获取数据的有效方法，通常是通过使用索引完成的。索引是对数据库表中 - - y i j 或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。 通常，数据库系统采用逐行扫描的策略查询整个关系表找到所有匹配的记录。如果在 某个表里有多条记录，但查询结果只有少数几行，则逐行扫描方法的效率会很低下。如果 让数据库系统在条件字段上支持一个索引用于定位匹配的行，则数据库系统只需要在搜索 树中进行少数几层的扫描就可以找到匹配行。由于避免了对整个表的扫描，减少了对磁盘 的访问量，查询效率得到大幅度提高。 随着社会的发展，信息量的迅速扩充，出现了很多大型数据库，存储n 维数据。在这 种情况下，传统的索引关键字类型已经不能满足用户的查询需要，对象关系型d b m s 的发 展必然要求索引关键字类型的可扩展性。而关键字的扩展性也会对传统索引结构提出新的 要求。此外，用于索引的属性的维数对索引结构的选择也有着重要影响。 2 1 索引关键字的数据类型对索引的影响 索引记录通常由关键字和指针构成，因此索引与关键字之间有着密不可分的关系 索引必须建立在索引关键字之上，以关键字的值约束查询范围。索引结构的发展也是索引 关键字类型不断拓展更新的必然产物，每出现一种新的数据类型都一定会带来索引方法的 更新和发展。 2 1 1 传统关键字类型的查询局限性 传统的d b m s 只能理解、存储和处理比较简单和固定的传统数据类型。如整数、浮点 数、字符串、日期、货币等。而复杂的数据类型只能由用户编写程序，借助高级语言功能 用简单的数据类型来构造、描述和处理，这就加重了用户的负担，也不能保证数据的一致 性。当然，这些简单的数据类型也完全不能满足用户的查询需求，例如：有一个全国的河 流统计表： c r e a t et a b l er i v e r ( n a m ev a r c h a r ( 3 0 ) ， o r i g i nv a r c h a r ( 3 0 ) ， l e n g t hn u m b e r ， s h a p el i n e ) ； 5 江 苏 大 学 硕士 学 位论文 其中s h a p e 属性描述了河流的形状，在地图上河流可以由多个直线线段表示，所以在 这里我们用l i n e 表示其类型。显然，s h a p e 不是一个传统属性，在地图上，我们可以利用 s h a p e 属性直观的对河流流经的城市进行查找，但却不能直接从数据库中查询该属性。 随着数据库使用领域的扩大，一些应用要求数据以二维或更高维的形式出现。特别是 g i s 的发展，提出了空间数据类型的概念。用户开始可以对空间属性进行查询。即上例中 的l i n e 类型可以定义成一个新空间类型l i n e ( p l ，p 2 ，p 。，p a r a m e t e r ) 其中p i 为曲线 顶点，为p o i n t 类型；p a r a m e t e r 为曲线的参数。但是随着数据库在多媒体、数据挖掘、 信息统计等领域的应用，用户的查询已经不仅仅局限于传统数据类型和空问数据类型。例 如，用户在进行图像检索时，输入查询条件“找到在图片左上角出现了太阳的图片 ，对 于这样的查询，d b m s 就无法处理。显然，传统数据类型无法表示客观世界中的复杂对象， 即结构复杂、相互联系的语义也十分复杂的对象。从而限制了数据库处理图形、图像、c a d 图件、声音等多种复杂对象。此外，传统数据模型也无法揭示数据之间的深层含义和内在 联系，缺乏数据抽象。 显然，这些基本的数据类型以及相应的查询谓词不能满足用户的需要，用户真正需要 的功能是可以在数据库中创建有相应操作符和操作函数的自定义数据类型。也就是需要数 据库管理系统具有“基本类型扩充 的功能。对象关系d b m s 具有扩充新数据类型的机制， 消除了类型模拟带来的效率问题。这样用户就可以根据实际的应用环境，定义合适的特定 数据类型。我们知道，一个数据类型定义为若干个对象和在这些对象上执行的各种操作的 集合体。因此，用户在定义一个新的数据类型的同时，需要定义相应的查询谓词以及操作 方法。下面，我们就用户自定义类型和查询谓词的问题进行研究。 2 1 2 用户自定义类型的研究 文献f 9 】中提到，一个好的对象关系型数据库管理系统( o r d b m s ) 除了具有原来关系 型数据库管理系统( r d b m s ) 的各种特点外，还应具备的四个基本特性是：基本类型的 扩充，复杂对象，继承性和规则系统。其中基本类型的扩充就是允许用户根据应用需求自 己定义数据类型及其方法。 用户自定义类型( u s e r - d e f i n e dd a t a t y p e ，u d t ) 是指1 1 0 】，用户根据自己的需要，创 建了一个在原始数据库中并未包含的数据类型，并指定适用于它们的操作。一般来说，这 种数据类型都是复合类型，由多个基本类型或是复合类型构成。在数据库中，可以将其作 为新的基本类型使用。u d t 的引入是关系型数据库管理系统( r d b m s ) 向对象关系型数 据库管理系统( o r d b m s ) 过渡的第一步。 6 江 苏大 学 硕 士 学 位论文 目前，所有流行的关系型d b m s 供应商都用某些面向对象的性能来扩展他们的产品。 i b m ，i n f o r m i x 和o r a c l e 都把他们的传统关系数据库扩展成为了对象关系“通用服务器 。 这些服务器扩展了数据库的存储能力和d b m s 本身的功能。而每个供应商都采用了不同的 机制来实现通用服务器概念。在文献【1 1 1 中提到，i b m 中的机制称为d b 2 扩展器( d b 2 e x t e n d e r ) ，i n f o r m i x 称这种扩展为数据刀片( d a t a b l a d e ) ，o r a c l e 则称之为数据架( d a t a c a r t r i d g e ) 。它们提供了预先包装的抽象数据类型( a b s t r a c td a t at y p e ，a d t ) 集合，包括 a d t 方法代码，向系统自动加载a d t 的d d l 脚本以及某些情况下数据类型的特殊存取方 法。组件式a d t 扩展类似于面向对象编程语言中的类库：它们提供一组完成共同任务的 对象，应用于某些特殊领域或专业。显然，这些扩展机制都包括了对u d t 的支持。也正 是由于u d t 的使用，d b m s 的扩展性得到了很大的提高。 用户自定义数据类型的特点： 1 复杂的数据结构。u d t 数据结构一般比传统数据类型复杂，有时甚至比空间数据 类型还要复杂的多。它们经常会由多个整型、字符型、空间类型，甚至一些用户自定义类 型共同构成，例如，超市对业务管理时，需要涉及货物、配送、顾客等方面的信息。为了 方便管理，可能不会将顾客信息用一个单独的关系表表示，而是采用一个“c u s t o m e r l d 的数据类型作为其业务表的一个属性。 c u s t o m e r l d ( n a m es t r i n g ， a r e af l o a t ， c a r d l di n t ， h o m e p o s i t i o np o i n t ) ： 在这个u d t 里，就有s t r i n g 、f l o a t 、i m 、p o i n t 四种数据类型。其中p o i n t 是一个 空间类型，如果在系统中没有对其作定义，用户还需要自行定义该类型。因此，在一个关 系表里，不太可能用一个固定长度的记录大小来表示u d t 。 2 数据类型的动态性，可能这个自定义的数据类型会经常要根据用户的实际需要被用 户进行修改，即可能出现并发的插入、删除等更新动作。 3 没有也不会出现对u d t 操作标准的定义。也就是说，不会出现针对u d t 的标准操 作集。对u d t 的操作基本由用户的使用环境决定。 4 u d t 的计算费用要比一般的关系操作甚至是空间操作的开销还要大。 5 系统仅通过一定的操作来控制某个u d t ，而这些操作是该数据类型所特有的。 7 江 苏 大 学 硕士 学位 论文 6 _ 个u d t 内部实现的变化将不会影响到程序的其余部分，只要该数据类型仍提供 同样的操作功能，唯一需要改变的地方是直接访问数据类型内部表达的操作代码部分。 我们知道，一个数据类型的定义为若干个对象和在这些对象上执行的各种操作的集合 体。因此，不论程序处理的是系统预定义的数据类型还是用户自定义的数据类型，都必须 考虑对象和操作这两个方面。下面- d , 节，我们将对不同数据类型的相关操作问题进行讨 论。 2 1 3 传统查询谓词的局限性 查询谓词作为一种运算符，用于查询一系列对象的某个共同特性或是对象间的一种关 系。它应该是在两个隶属于同一个类型的运算分量问进行的操作。而且，由于具体的运算 总会和特定的数据类型相关，因此查询谓词的定义和具体数据类型的定义应该紧密联系在 一起。总的来说，查询谓词是对查询树进行遍历的依据，是查询操作的基础。 下面，我们研究一下传统查询谓词的局限性： 1 对于h a s h 索引来说，只有一个查询谓词，就是“等于”，也可以用操作符“= 来 表示。例如，以年龄为关键字，定义h a s h ( a g e ) = a g em o d1 2 ，则把所有的人按年龄分 成1 2 组，在查找时，可以直接按照“等于 谓词，找到该年龄所在分组，然后再进行线 性寻址搜索，寻址效率可以提高1 2 倍。 2 对于b 树索引来说，可以有“小于 、“小于等于”这两种比较谓词，对于操作符 可以设为“ 和“”。在比较时，要根据具体的操作整型，定义实际的比较谓词，索 引在查询过程中会根据操作数据类型( 如两个i n t l 6 数据的比较，或是一个i n t l 6 与一个i n t 3 2 的比较等) ，选择合适的谓词。 这两类谓词都用在一维属性的查询中的，且查询谓词两端的数据类型也都要求是传统 数据类型。显然，由于两类谓词的局限性造成了索引方法在查询操作上的局限性，即只能 对传统数据进行查询。 3 为了扩展索引的应用范围，需要对查询谓词进行扩展。类属b 树n 2 1 就是一个通过 扩展查询谓词实现b 树索引通用性的实例。类属b 树将查询谓词抽象为“l e s st h a n 和 “l e s s o r e q u a l ”，对于谓词两边的比较数据类型不作限制，扩展了可查询数据类型的范围。 目前，类属b 树已经可以用在对空间数据类型的检索上。用户可以根据应用系统的实际需 要定义这套查询谓词的物理意义，编写相应的操作函数。比如使用扩展b t r e e 索引一个图 像集时，就可以进行“图像x 和图像y 是否相等”，“图像x 是不是比图像y 小”、“图像x 是否大于图像y ”这类查询。当然，在查询前，需要定义比较谓词“等于”、“小于、“大 r 江苏大 学 硕士 学 位论文 于 的物理含义。 4 k - d 树【1 3 】的每个结点表示k 维空间的一个点，树的每层根据本层的分辨器 ( d i s c r i m i n a t o r ) 作出分支决策。这个分辨器相当于一个比较谓词，是对数据在本层对应维 上的一个大小比较谓词，根据查询关键字与当前结点在d 维( 当前结点在i 层，d = im o dk ) 上的比较，决定是沿着当前结点的左分支还是右分支继续查找。即查询谓词的两端是两个 k 维空间点在i 维上的分量值，这个分量值也是整型数据。 5 r 树的每个结点是一个k 维空间中的最小包围矩形，在对该查询树进行遍历时，最 常用到的查询谓词是“包含( c o n t a i n s ) 。即当索引关键字包含在当前结点的某个记录中时， 查询可以会沿着该记录继续向下进行。除此以外，r 树的查询谓词还包括“o v e r l a p ( 重叠) ”、 “e q u a l 等。查询谓词两端的数据都是空间坐标类型的数据。 显然，这两类空间查询谓词也会限制查询树的查询范围。比如说，对于“找出所有马 的图像”或者“找出所有曝光过头的图像”这样的查询，r 树等空问索引方法就无能为力 了。这是由于这两类索引谓词的使用局限性所造成的。对于空间数据以外的数据类型，查 询谓词不能识别。而用户自定义类型是超出了传统数据类型和空间数据类型的，因此传统 比较谓词和空间查询谓词不能完全满足其需要。随着数据库系统的发展，用户自定义数据 类型也会越来越普遍。这带来的一个重要问题就是，必须要有具有扩展性的索引方法，才 能对这些自定义数据类型进行有效查询，系统性能和开发时间才能得到提高。 2 1 4 用户自定义类型对索引的影响 由于传统数据类型的局限性，在传统数据类型上发展起来的传统索引方法也只有有限 的几种：散列( h a s h ) 、无序索引、顺序索引、稀索引、多级索引、结构化索引等。其中 结构化索引中包括二叉树索引和b 树索引等。其中，最成功的是b 树及其变种b + 树，目 前每一个成功的关系d b m s 都采用了b 树。但即使是b 树，传统的索引方法也都只能检 索一维的传统数据类型。 其中有一些已不能由传统的索引查询，因此人们开始设计一些特殊的索引结构来处理 多维数据类型。如，随着g i s 的快速发展，出现了很多空间数据类型，由于空间数据类型 的结构上的复杂性，空间操作的不封闭性等问题，传统索引方法无法解决，因此人们开发 了专门用于查询空间数据类型的空间索引。此外，根据空间实体是点类型还是区域类型， 空间索引的选择也会有不同。目前比较常用的空间索引有k d 树、r 树等。 虽然已开发了空间索引，但对于某些一维索引能解决的查询问题还是用高维索引做的 话，系统的查询效率会受到影响。例如这样一个查询实例： 9 江 苏大 学 硕 士 学 位论文 s e l e c l 。n a m e f r o mc o u s t o m e r l d w h e r el o c a t i o nn e q u a t o r e q u a l sp o i n t ( 2 0 0 ，0 ) ； 这个查询是要找出所有住所与赤道的距离与点( 2 0 0 ，o ) 与赤道的距离相等的客户姓 名，即所有住所在赤道以北2 0 0 英里内的客户。用户定义的查询谓词“l o c a t i o n ne q u a t o re q u a l s ”表达了该查询要求。系统当然可以采用r 树方法对每个客户的住所是否 满足查询要求进行二维查询。但是如果可以对“住所在赤道以北的距离 建立b 树索引， 则系统的执行效率就行得到很大的提高。由此提出的类属b 树方法就解决了此类问题。可 见，用户自定义的数据类型及查询谓词会要求索引具有扩展性。而传统的查询树结构都是 针对某一种特定类型的数据而构造，显然不能满足用户自定义类型数据的查询要求。 u d t 可以看作是一种类似于类库的面向对象的软件包，用于某个特定领域，它不像 传统的数据类型一样具有某些规律性，因此，传统的索引方法在对用户自定义数据类型进 行检索时会出现很多问题，以致索引的查询效率受到了很大影响，有时甚至不能支持对它 们的检索或是连接查询。因此，系统对自定义数据类型的支持必然会对索引提出可扩展性 的要求。需要开发更具扩展性的索引方法，提高对用户自定义数据的查询效率。 2 2 索引关键字的维数对索引的影响 在上小节我们讨论了索引关键字的数据类型对索引的影响，即根据待查询的数据类型 的差别，我们会选择不同的索引方法。当然，索引关键字除了在数据类型上对索引的选择 会有影响，在维数上也会对索引结构的选择有着很大的作用。这一小节，我们将以关键字 维数为参数，研究关键字维数在索引方法选择中的作用。 2 2 1 索引关键字维数对索引的影响 固有属性是数据对象的特有属性，可以作为区分对象的依据。空间属性则描述了对象 的地理位置，以及与其它对象的空间位置关系等。由于空间属性和固有属性的相异性以及 属性自身性质的特殊性，建立索引时，应该根据这两点选择索引的结构。下面，我们以索 引关键字的属性为参考，对索引的选择做一些讨论： ( 1 ) 建立在一个一维传统属性上的查询。这是一种用传统索引方法就可以解决的查 询问题。例如，在学生管理系统中，需要查询信息系( i s 系) 的全体学生“s e l e c ts n of r o m s t u d e n tw h e r e s d e p t = i s 一，此时可以在属性域s d e p t 上建立一维索引。对于这种简单 的查询，一般采用b 树、b + 树、h a s h 等一维排序索引方法即可完成。 ( 2 ) 建立在一个二维空间坐标属性上查询。如在中国地图中，查找位于江苏省内的 1 0 江苏大 学 硕 士 学 位论文 所有县( 市) 。对于这类查询，可以将索引建立在县( 市) 记录的位置属性l o c a t i o n 上。一 般可采用r 树及其变体、k d b 树【14 1 、h i l b e r t 曲线等方法解决。不过用户也需要根据 实际检索的空间数据类型采用不同的索引结构。例如，对于空间点数据类型的检索，通常 会采用k d b 树、格网文件1 1 6 】以及r 树等索引方法；而对于非点状空间一般都采用r 树 方法，也可以使用h i l b e r tr 树i l ”方法。另外，类属b 树的出现使得一些空问类型的关键 字也可以用它来进行检索。例如，在一个二维直角坐标系中的p o i n t 类型数据集，若在查 询时，只需要对数据按照x 轴上的坐标排序，则用类属b 树就能快速完成检索，而不需要 使用r 树。这样就极大的简化了查询过程，提高了查询效率。 ( 3 ) 建立在两个传统属性上的联合查询，两个索引关键字可以用八连接，但不能用 v 连接。例如查询所有主修课( m a j o r ) 选了“d a t a b a s e ，选修课( m i n o r ) 选了“m u s i c ” 的所有学生。此时，索引就建立在联合属性( m a j o r ，m i n o r ) 上。这种查询属于多字段查 询，目前的索引方法中只有b 树方法可以对其进行检索，但是却需要通过两次调用b 树方 法来实现。由于索引文件存储在磁盘上，因此这样的查询方法会降低系统的查询效率。 ( 4 ) 建立在一个空问属性和一个传统属性上的二维联合查询。例如，在学校硬件管 理系统中，查找以图书馆为核心，半径2 公里以内的所有教学楼。此时的索引建立 b l i f u n c t i o n 和d i s t a n c e 这两个属性上，其中d i s t a n c e 是在空间数据类型l o c a t i o n 上的一个 操作函数。在目前对于这样的查询，都是采用空间索引+ 一维顺序索引的方式进行。系统 需要两次从外存中调用不同的索引文件，极大的影响了系统的查询效率。 ( 5 ) n 维属性的联合查询，这是在( 4 ) 基础上的延伸，即用于检索的这n 个属性中 既包括固有属性，也包括空问属性。例如，一个旅游开发商想知道自己的地产中，有哪座 山适合滑雪初学者使用。此时，索引需要建立在l o c a t i o n ( 位置) 、h e i g h t ( 山的高度) 、