（计算机软件与理论专业论文）多维数据及时态数据索引研究.pdf

中山大学博士学位论文 论文题目： 专业： 博士生： 指导老师： 多维数据及时态数据索引研究 计算机软件与理论 吴凌坤 汤庸教授 摘要 随着计算机科学的发展和计算机应用的广泛化，计算机中处理的数据越来越 复杂。相应地对各种复杂数据的处理也成为了计算机科学中的热点问题。在复杂 数据中多维数据类型和时态数据类型的应用非常广泛。多维数据可以分为两类， 一类是其本身意义是多维的，比如空间数据；另一类虽然本身并不是多维的，但 是在实际应用中把它看做多维处理却更加自然和方便。多维数据的应用必将随着 应用的深入越来越广泛。时态数据广义上也可看作是一类多维数据，但是时态数 据有其自身的特点，比如独有的时态变元等。时态数据在电子政务，证卷，银行， 保险等多个商业领域都有重要意义。而现有商业数据库中的关系数据索引并不适 应多维数据和时态数据的存取，从而使得多维数据和时态数据的索引研究具有理 论和应用价值。 本文对多维索引和时态索引进行了深入研究，其主要贡献如下： 本文系统地综述了现有多维索引的研究状况，并通过分析主要多维索引 的特点和不足之处，提出了一种新的多维点索7 1 ：d h p r - t r e e 。其基本结构基 于r 木t r e e ，通过兄弟叶节点均匀机制增加了整个索引的负载，延缓了叶节 点的分裂；通过叶节点动态重构机制有效减少了叶节点层乃至整个索引结构 的重叠区域；通过引入并改进虚拟外包矩形的概念，大大增加了节点的扇出； 还通过引入动态有效维机制大大减少了多维下节点内的冗余信息，进一步提 高了节点特别是高层节点多维情况下的扇出。 本文给出了d h p r - t r e e 详细的查询算法和更新算法，并给出算法解释和 流程图，对其中复杂的算法还给出了例子。然后为多维数据设计了系统详细 的实验，通过大量实验，可以证明d h p r - t r e e 在多种分布的数据中都能保持 范围查询和点查询的高效性，并且结构紧凑，物理利用率高，同时其维护代 h i 摘要中山大学博士学位论文 价仍然是可控制的。 本文给出了一个时间期间集合上的数学框架。本文基于时间期间的内在 特性，研究了时间期间集合上的数学关系，提出了时态等价关系和时态拟序 关系，由此引出了时间期问集合上的时态线序和时态线序划分的概念，并提 出了两种对于索引结构非常有意义的划分方法，即最小线序划分和最长线序 划分。还分别给出了得到这两种线序划分的算法，其正确性证明和时间复杂 度分析。 本文对时态数据及时态索引进行了研究。针对传统关系模型表达能力不 足，不适合时态数据的缺陷，本文将时态信息结合到面向对象数据模型。本 文通过分析时态对象数据的特点，提出了时态对象数据模型t o q d m ，并在时 态对象数据模型和其时态类图的基础上，通过对时间期间集合上时态等价关 系的应用，得到了时态数据摘要t o s u m 。然后结合时态数据摘要和时间期间 集合上的线序划分算法，提出了时态对象索引t o d i m ，并给出了其查询和更 新算法。最后通过仿真实验和基本评估表明了所提出时态对象索引的可行性 和有效性。 关键词：多维索引，时态对象数据模型，时态索引 i v 巾山大学博+ 学位论文 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： r e s e a r c ho nm u l t i - d i m e n s i o n a ld a t aa n d t e m p o r a ld a t ai n d e x c o m p u t e rs c i e n c e l i n g k u nw u y o n gt a n g 。 a bs t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n dt e c h n o l o g ya n da p p l i c a t i o n s ，t h e d a t a t y p e s w h i c hc o m p u t e rd e a l i n gw i t hb e c o m em o r ea n dm o r e c o m p l e x c o r r e s p o n d i n gd a t as t r u c t u r e sa n da l g o r i t h m so nt h o s ec o m p l e xd a t at y p e sa r eh o t s p o t si nr e s e a r c ho fc o m p u t e rs c i e n c en o w a d a y s m u l t i d i m e n s i o n a ld a t aa n dt e m p o r a l d a t aa r eb o t h p o p u l a rc o m p l e x d a t at y p e s m u l t i - d i m e n s i o n a ld a t aa r eu s e d e x t e n s i v e l yi nt w ow a y s ，o n ei sg e n e r a lm u l t i d i m e n s i o n a ld a t aa si t sm e a n i n g ，s u c ha s s p a t i a ld a t a ；t h eo t h e r i sc o m m o nm u l t i a t t r i b u t e sd a t ab u ti sd e a rw i t ha s m u l t i - d i m e n s i o n a ld a t a a n dt e m p o r a ld a t a , g e n e r a l l ys p e a k i n g ，i sa l s oak i n do f m u l t i - d i m e n s i o n a ld a t a , b u ti th a sc h a r a c t e r i s t i c so fi t so w l lt e m p o r a ld a t ai sv e r y i m p o r t a n t ，a n de v e nb e c a m et h e c r i t i c a lf a c t o ri n m a n ya p p l i c a t i o n s ，s u c h a s e g o v e r n m e n t ，s e c u r e r s ，b a n k i n g ，i n s u r a n c e ，e t c t r a d i t i o n a li n d e x e so nr e l a t i o n a l d a t ai nc o m m e r c i a ld a t a b a s es y s t e m sa r en o tf i tf o rm u l t i d i m e n s i o n a ld a t aa n d t e m p o r a ld a t a ，t h e r e f o r e ，r e s e a r c ho nm u l t i d i m e n s i o n a ld a t ai n d e xa n dt e m p o r a ld a t a i n d e xh a v eg r e a tt h e o r e t i c a la n dp r a c t i c a lv a l u e t h i sd o c t o r a lt h e s i st h o r o u g h l ys t u d i e st h em u l t i d i m e n s i o n a ld a t ai n d e xa n d t e m p o r a ld a t ai n d e x t h em a i nc o n t r i b u t i o n sa r el i s t e db e l o w ： f i r s t l y , t h i s t h e s i s s y s t e m a t i c a l l y s t u d i e st h er e s e a r c hf i e l d so f m u l t i d i m e n s i o n a li n d e x , a n da f t e rd i s c u s s e st h ea d v a n t a g e sa n dw e a kp o i n t s o fs e r v a lp o p u l a rm u l t i d i m e n s i o n a li n d e x e s ，an e wm u l t i d i m e n s i o n a lp o i n t a c c e s sm e t h o d ：d h p r - t r e ei sp r o p o s e d i t sb a s i cs t r u c t u r ei sb a s e do n r * - t r e e t h es i b l i n gl e a fn o d e sr e a l l o c a t i o nm e c h a n i s mg r e a t l yi n c r e a s e st h e v 摘要中山大学博十学位论文 l o a do fl e a fn o d e s ；d y n a m i cl e a fn o d e sr e o r g a n i z a t i o nm e c h a n i s me f f e c t i v e l y r e d u c e st h eo v e r l a p sa m o n gt h el e a fn o d e s b yi n t r o d u c i n ga n di m p r o v i n gt h e v i r t u a lb o u n d i n gr e c t a n g l em e c h a n i s m , f a n o u t so fa l ln o d e sf i r e g r e a t l y i n c r e a s e d a n db yt h ea d a p t i n gt h ed y n a m i ca c t i v ed i m e n s i o nm e c h a n i s m , m o s tr e d u n d a n c i e si nn o d e s ，e s p e c i a l l yt h eh i g hl e v e ln o d e sa r ee l i m i n a t e d ， w h i c hf u r t h e ri n c r e a s et h ef a n - o u to fn o d e t h ed e t a i l e dq u e r ya l g o r i t h m sa n du p d a t ea l g o r i t h m so fd h p r - t r e ea r e p r o p o s e d t h e nt h r o u g he x t e n s i v ea n dc o m p r e h e n s i v ee x p e r i m e n t s ，i tc a nh e s e e nt h a td h p r - t r e ei sac o m p a c ta n de f f e c t i v em u l t i - d i m e n s i o n a lp o i n t i n d e xi nm a n yd i s t r i b u t i o n s ，a n di t si n s e r t i o nc o s ti sa c c e p t a b l e t h i st h e s i sp r o p o s e sam a t h e m a t i cf r a m e w o r ko nt i m ep e r i o ds e t f i r s t ，i t s t u d i e st h em a t h e m a t i c a lr e l a t i o n si nt i m ep e r i o ds e t ，p r o p o s e st e m p o r a l e q u i v a l e n c er e l a t i o na n dt e m p o r a lq u a s i - o r d e rr e l a t i o n a n db a s e do nt h e s e r e l a t i o n s ，i td e f i n e st e m p o r a ll i n e a ro r d e rt e m p o r a ll i n e a ro r d e rp a r t i t i o n , a n d t h e nf u r t h e rp r o p o s e st w ok i n d so fu s e f u ll i n e a ro r d e rp a r t i t i o nt o g e t h e rw i t h t h e i rc o r r e s p o n d i n ga l g o r i t h m s t h i st h e s i st h o r o u g h l ys t u d i e st h et e m p o r a ld a t ai n d e x d u et ot h el a c ko f e x p r e s s i v ep o w e ro ft r a d i t i o n a lr e l a t i o n a ld a t am o d e l ，o b j e c t o r i e n t e dd a t a m o d e la r ec h o s e nt oi n t e g r a t ew i t ht e m p o r a li n f o r m a t i o n f i r s tt h et e m p o r a l o b j e c t - o r i e n t e dd a t am o d e lt o q d mi si n t r o d u c e d ；t h e nb a s e do nt o q d ma n d t e m p o r a le q u i v a l e n c er e l a t i o n , t e m p o r a lo b j e c t - o r i e n t e ds u m m a r yt o s u mi s d e v i s e d ；t o g e t h e rw i t ht o s u ma n dt e m p o r a lq u a s i - o r d e rr e l a t i o n , t e m p o r a l o b j e c t o r i e n t e dd a t ai n d e xt o d mi sp r o p o s e d e x p e r i m e n t sa n de v a l u a t i o ni n t h ee n dp r o v et h ev a l i d i t ya n de f f e c t i v eo ft o d i m 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 ai n d e x , t e m p o r a lo b j e c t - o r i e n t e dd a t am o d e l ， t e m p o r a ld a t ai n d e x v i 中山大学博士学位论文 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 v i i 学位论文作者签名： 飘群 日期：涉一爷罗月；日 f 中山大学博士学位论文 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 皲辞 日期：2 0 矿兮年r 月1h 。 i x 中山大学博士学位论文 1 1 研究背景和意义 第1 章引言 自从2 0 世纪4 0 年代第一台计算机诞生以来，计算机的应用就和数据处理紧 密结合在一起。计算机在运行中需要不停地得到数据和存储数据，这就使得数据 存取技术在整个计算机科学中占有十分重要的地位。且随着计算机在科学计算方 面的应用不断扩大，计算机中处理的数据量也越来越大，使得一个程序所需的数 据在不能完全存储在内存之中，随之应运而生的就是第二存储器( 外存) ，其中 最常用，最为人们所知的就是温切斯特硬盘( w i n c h e s t e r ) ，也就是人们通常称之 为的硬盘。除此之外还有磁带，磁盘等。内存特点是存取速度快、容量小，但价 格高，断电后数据即丢失；而第二存储器的特点是容量大、价格低、存储持久， 但存取速度慢。这就使得外存的存取成为整个应用系统的瓶颈所在，如何管理并 优化外存存取，曾经是2 0 世纪7 0 、8 0 年代的热门课题。随着外存存取技术发展 而日益成熟起来的就是数据库技术。数据库技术在商业和工业中的成功运用使得 计算机的应用领域大大拓展。 进入2 0 0 0 年后，网络信息化浪潮席卷全球，各行各业都在向着数字化，信 息化方向迈进。当下真正是处在一个信息爆炸的时代，计算机中处理的信息量更 是成几何级数增加。这时，传统的数据库的存储技术已经远远不能够满足实际应 用的需要了。这主要体现在以下几个方面：第一，数据量巨大，传统的数据库不 能或不能很好的处理如此巨大的数据量；第二，数据模型复杂化，现在成熟的数 据库技术都是建立在关系数据模型基础上，以二维表( 关系) 为基础，但二维表 的表达能力弱，已经不能适应当代的面向对象数据、x m l 数据、空问数据和时态 数据等等复杂数据类型；第三，由于网络的发展和数据量的增加，数据存储趋势 已经从传统的集中式逐渐转变为分布式。 在传统的数据库中，索引技术是关键技术，它使得人们能快速的存取数据库 中的数据。处在当前这个信息爆炸的时代，到处都是数据，如何建立合适的索引， 从而使得用户能快速有效的得到其想要的数据，更是摆在当代研究人员面前的研 究热点和难点。 1 中山大学博十学位论文 在当代应用中，很多数据的处理都可总结为对多维数据的处理，多维数据可 分为两类，一类是现实意义上的多维数据，比如空间数据( 经度维，纬度维) 、 时态数据( 有效时间维，事务时间维) ；另外一类是本来不是多维数据，但按照 多维数据处理，比如所有学生的身高、体重和年龄就构成了一个三维的数据立方 体，不同d n a 的各种染色体数据就构成多维的数据项。为了能快速存取多维数 据，多维索引也就应运而生。多维数据的索引起源于2 0 世纪6 0 、7 0 年代，在 8 0 、9 0 年代达到一个高潮。多维索引的研究是非常有现实意义和研究价值的， 对实际应用( 如地理信息系统g i s 等) ，和其他学科的科学研究均有很大的帮助。 在多维数据中，时态数据是比较特殊的一类。时间是自然界无处不在的属性 1 】，是事物的固有属性，其应用和意义是十分广泛的。时态数据是多维数据， 但是时态数据中有效时间和事务时间都有专门的时态变量n o w 和u c 2 7 】，这 两个变量随着时间的变化而变化其值。而其他多维数据并不具备这种变量，故时 态数据和多维数据是有区别的，相应的时态索引和多维索引也应有区别。时态索 引的研究起源于2 0 世纪8 0 年代初，在2 0 世纪8 0 到9 0 年代研究非常活跃，进 入2 0 0 0 年后，时态索引的研究主要处于将理论应用于实际的阶段。 因为传统的索引技术并不适用于多维数据，更不适用于多维数据中的时态数 据。在本文中，作者对多维索引和时态索引进行了详细的研究。 1 2 研究内容和创新点 本文的研究工作是在国家自然基金( 6 0 3 7 3 0 8 1 ，6 0 6 7 3 1 3 5 ) ，广东省自然科学基 金( 0 5 0 0 3 3 4 8 ) ，教育部“新世纪优秀人才支持计划 资助项目的支持下完成的。 本文工作为t e m p d b 课题的部分内容。下面具体列举本文的创新点。 提出多维点索引d h p r - t r e e 本文首先精细分析了多维下数据的特点及r 乖t r e e 8 】自身的特点，然后提出 了一种多维点索引结构d h p r t r e e ( d y n a m i ch i g h - d i m e n s i o n a lp o i n tr - t r e e ) ，并 给出了其具体的查询算法和动态维护算法，最后通过大量实验验证了该索引结构 是在多种分布数据下都能保持高效紧凑的多维点索引。d h p r - t r e e 具体有以下创 新点： 通过引入和改进v b r 增加节点扇出 2 中山大学博士学位论文 d h p r - t r e e 引入了虚拟外包矩形并加以改进，将虚拟外包矩形实化使用，使 得节点的扇出大大增加。加大了d h p r - t r e e 在多维下的适用性。 通过引入和改进动态有效维概念去除节点冗余信息 d h p r - t r e e 引入了动态有效维概念，去除了高层索引节点中的冗余信息。节 点的有效维根据其实时信息动态调整，这样使得d h p r - t r e e 更能适应实际应用 的需要，可以减低建立索引人员做决策的难度。 通过兄弟叶节点均匀机制增加物理利用率 d h p r t r e e 通过兄弟叶节点均匀机制，有效增加了叶节点的负载( 叶节点所 包含的记录数) ，在提高叶节点负载的同时，也延缓了叶节点的分裂，减少了索 引结构的维护代价。 通过叶节点动态重构机制减少相交区域 d h p r - t r e e 引入了叶节点重构机制，有效的减少其叶节点间以至整个索引结 构的相交区域。精巧重构算法设计使得重构完成后各兄弟叶子节点拥有相同的负 载，即相同的记录数( 或差1 ) ，且各叶节点的最小外包矩形间完全没有相交。 这在一定程度上减缓了叶节点的分裂，使叶节点数量增加缓慢，物理利用率更高。 实现了d h p r - t r e e 并验证了其有效性 本文给出了多维点索引d h p r - t r e e 的具体查询和维护算法，然后设计了多维 数据的实验，并通过大量实验，验证了d h p r - t r e e 的有效性：即d h p r - t r e e 是 一种高效紧凑的多维点索引结构，且其维护代价是可控制的。 讨论并给出了一个时间期间集合上的数学框架 本文通过对时间区间集合本身特性的精细分析，提出了时态等价关系和时态 拟序关系。并基于时态拟序关系提出了时间期间集合上的线序划分问题，同时给 出了两种非常有意义的划分：最小线序划分和最长线序划分。本文还给出了得到 这两种划分的算法，以及其正确性证明和时间复杂度分析，最后形成了时问期间 集合上的数学框架。 提出了时态对象索引t o d i m 从数据模型的复杂度上看，关系数据和各种新型数据( 以半结构化数据和数据 空间等为基本代表) 处于问题的两级，而面向对象数据则位居其中，发挥着“连 接 或“承接”作用。对于时态数据而言，时态关系数据较为基本，新型时态数 3 中山大学博士学位论文 据较为复杂，而时态对象数据则因具有强大语义变大能力和相对坚实的研究基础 而呈现出其特有的研究意义与技术价值。本文通过对面向对象数据模型的研究和 对时态数据信息分析，提出了一个基于属性时间标签的时态对象数据模型；然后 在时态对象数据模型t o q d m 基础上，应用时态等价的约减，得到了时态摘要 t o s u m ；同时结合时间期间集合上线序划分算法，提出了时态对象数据索引 t o d i m ；另外本文还研究了t o d i m 的动态管理过程中增量式更新问题，并给出了 其更新算法；最后作者设计并完成了一个模拟实验以检验时态索引的有效性与可 行性。 1 3 本文的结构 本文以数据索引为研究对象和主线，共分为6 个章节，具体安排如下： 第1 章：即是本章。本文的引言部分。概要的介绍了论文的研究背景，研究 意义，以及主要的创新点。 第2 章：介绍了索引技术理论基础，主要是和本文相关的各种有代表性的索 引技术。 第3 章：本章首先概述了多维索引的研究状况。然后通过分析几种具有代表 性的多维索引的不足，提出了一种高效紧凑的多维点索引d h p r t r e e 。最后给出 了d h p r - t r e e 的结构定义，其静态特性和动态特性。 第4 章：本章主要是讨论多维索引d h p r - t r e e 的动态维护算法和对其效率的 验证。主要给出了d h p r - t r e e 的查询和插入算法，对于复杂的算法还给出了流 程图。然后详细设计了多维数据的实验，并通过大量实验验证了d h p r - t r e e 的 有效性。 第5 章：本章讨论的是时态索引技术。首先系统分析了时态数据索引的研究 状况，然后分析了面向对象模型应用于时态数据的优点，同时精细研究了时间期 间集合上的数序关系并给出了一个数序框架，并在时态对象数据模型和时态对象 摘要的基础上提出了时态对象索引模型。最后通过实验验证了所提出的时态对象 索引框架的有效性。 第6 章：本章为全文的总结。 4 中山大学博十学位论文 第2 章索引技术理论基础 这一章简要介绍索引技术的基础。首先用例子叙述索引在数据存取中的作 用，并给出一般索引的概要结构和衡量索引优劣的度量标准。然后介绍几种在当 代商业数据库中得到大量应用的有代表性的索引结构，分别是b + - t r e e 、h a s h 索 引和b i tm a p 索引。最后从不同的角度系统地对现有的索引进行分类，加深对索 引的理解。 2 1索引概述 2 1 1 索引的作用 索引是用来快速检索和访问数据的。图2 1 是个索引的简单例子。实际的职 工人数多( 数据表含大量元组) ，字段多( 列多) ，如果没有左面的索引表，查找 时即便知道了职工的职工号，寻找职工的记录也需要从数据表最开始遍历整个 表，逐一匹配。但如果有左面的索引表，因为索引值( 码) 通常是单个值，故索 引表数据量一般非常小，比如图2 1 的左图，只含有职工号和对应记录的物理地 址，此时根据记录的码查找记录的物理地址，再取得记录的信息就非常快速了。 索引表物理地址数据表 码物理地址 2 12 2 0 3 42 8 0 4 44 6 0 4 71 6 0 5 4 5 2 0 5 84 0 0 9 5 1 0 0 9 83 4 0 职工号姓名性别职务 9 5张三男讲师 5 4 李四男教授 4 4 孙娜 女讲师 9 8 李建国男助教 4 7王婷女 副教授 5 8 周庆男讲师 3 4 陈丽 女教授 2 1赵娟女助教 图2 1 索引示意图 考虑到外存访问 9 】9 与内存访问不一样，外存访问是以物理页物理块 ( p a g e b l o c k ) 为单位的，最少一次一页。当然顺序读取多页比单独访问多页要 快，但是为了方便理论研究，可以简单认为读写一个物理块就是一次i o 。又由 5 俩御拗狮狮蜘伽渤 中山大学博士学位论文 于进行_ _ 次i o 的时间大大高于一次内存读写的时间，故外存访问是以i o 次数 为效率衡量参数的。这样，索引在外存访问中就是非常必要的了。 具体举例说明。如果一条记录在磁盘上占用1 0 2 4 字节( 1 k b ，操作系统中 l k = 1 0 2 4 ) ，对其中只有几个字节的字段简历索引，不妨设索引字段长度为8 字 节( 类似于图2 1 左表，索引字段为两个h a t ) ，以s q ls e r v e r2 0 0 0 为例子，在 s q l s e r v e r2 0 0 0 中，一个物理页的大小为8 k b 。 这样，一页就能存储记录8 k b 1 l ( b = 8 ，即每页能存储8 条记录。同样的， 一页能存储索引条目8 k b 8 b = 1 0 2 4 ，即一页能保存1 0 2 4 个索引条目。 假如现在有8 0 0 0 条记录，又知道某项记录的码值，要查找该条记录的详细 信息。 如果没有索引，则最坏情况下需要遍历8 0 0 0 条1 0 2 4 字节8 k b = 1 0 0 0 页，即：必须要访问1 0 0 0 个物理页才能找到需要的记录。 但如果有索引，用索引来查找，则最坏情况下需要遍历8 0 0 0 条8 字节 8 k b 8 页就能得到该记录在索引表中的索引项，也就是获得该记录具体的物 理地址需要访问8 个物理页，此时，根据得到的具体的物理地址再访问一个物理 页就可以得到该记录的信息。即：一共只需访问8 + 1 = 9 个物理页就达到目的了。 没有索引和有索引的代价分别是访问1 0 0 0 个物理页和访问9 个物理页，这 里可以清楚的看到索引在数据存取中的作用。 索引的思想并不是计算机技术中独有的。现实生活中也经常运用到索引的思 想，比如书籍的目录，图书馆的数目编号等都是索引思想的很好运用。 2 1 2 索引的结构 索引文件通常包含如下形式的记录： 具有上面形式的记录称为索引项索引记录( i n d e xe n t r y ) ，其中s e a r c h _ k e y 是索引码，用于查找文件中记录的属性集。p o i n t e r 是指针，用来指示该索引码 所代表的记录的具体物理位置。 索引码不一定是单值的，但其大小通常比具体记录小很多。索引文件也比原 始数据文件小很多。索引文件的内容通常是动态的，随着数据文件内容的变化而 6 中山大学博十学位论文 更新。这也意味着索引除了占用额外的空间外，还有其他副作用的存在，即需要 动态的维护。 2 1 3 索引度量标准 索引的优劣有很多度量标准，主要有： 存取效率 这是索引存在的价值，当然也是其优劣的度量标准。 有效支持的存取类型 比如按记录某个属性的给定值进行存取，还有按记录某个属性的给定区间进 行存取等等。这决定了索引适用的范围大小。 索引的维护代价 主要有插入代价、更新代价和删除代价。维护代价小的索引可以用在记录频 繁更新的数据库中。维护代价大的索引可以用在数据仓库等数据几乎不会变 化的地方。 索引所占物理空间 索引所占的物理空间大小除了受到索引码大小的影响外，还直接受到索引物 理利用率的影响。因为索引多是动态维护的，一般不可能使得每个物理页都 填满索引项。物理利用率高的索引，每个物理页使用的部分越多，则所含索 引项就越多，相应的，整个索引所使用的物理页就越小，索引文件就越小。 2 2 几种主要索引介绍 这一节将介绍几种现在商用数据库中运用最为广泛的索引技术：b + - t r e e 1 0 】 索引、h a s h 1 1 索引和位图索：j l 1 2 。 2 2 1b + - t r e e 索引 b t r e e 1 3 ，1 4 1 索引是一大类索引，一般提到的b t r e e 分为两种：原始的 b t r e e 和b t r e e 的改进型：b + - t r e e ，几乎所有的数据库都支持b + - t r e e 这种数 据结构，因此，在下面将着重介绍b + - t r e e 。 7 巾山大学| 尊士学位论文 b + - t r e e 是一棵平衡多叉树( a v l 树) ，所有的索引项均保存在叶子节点上， 内部节点只指示路由，并不保存实际信息。b + - t r e e 具有以下特点： 其所有的叶子节点都在同一层上； 每一个节点都是和磁盘叶面大小一致，并存放在磁盘上的某个合适位置。 根节点以下的，所有节点都至少是半满的。即除了根节点以外，它的所 有节点最多有m 一1 个值和m 个指针，最少有厂耽2 一1 个值和r 所2 个 指针，即是说一颗m 叉的节点含有 r m 2 ，聊 个非空孩子； 典型的内部节点结构为： p i ，k l ，p 2 ，k 2 ，p 即l ，k 小t ，p 其中b 为指向第f 个孩子的指针，墨为第f 个查找的键，且满足k i k 2 k n ，p ，所指子树中所有孩子查找键值均小于k ，故当要搜索的记录键值大 于墨，小于墨+ ，时，则访问该节点b + j 所指的孩子节点。 叶节点储存所有相应值的物理地址的指针，即是上面说的索引项。 大多数b + - t r e e 在叶节点层的节点还有一个额外的指针：顺序指向下一 个叶节点，这样把所有的叶节点串起来，以方便范围查找。 图3 2 是一棵三阶b + - t r e e 的例子，可以看到左面孩子的所有查找键值都是 小于该键值的，比如对于根节点来说，b r i a n 、d a d 和m a r s h 的字母序都是小于 p e t e r ，而p e t e r 、r e d 、r o u n d 的字母序都是大于等于p e t e r 。另外，b + - t r e e 内部 节点不存储具体索引项，这样使得所有查找路径长度都是一样的。且b + - t r e e 的 叶节点是按顺序用指针连接起来的，方便范围查询。 p e t e r m a r s hr e d ! b d a nd a d h m a r s h 卜叫 p e t e r h r e dr o u n d 图3 2 三阶b + - t r e e 8 巾山大学博士学位论文 在实际应用中，通常b + - t r e e 一个节点的大小为一个物理页的大小。在含有 刀个关键字的b + - t r e e 上进行查找时，从根节点到关键字所在的叶节点路径上涉 及的节点数不会超过1 0 9 r 册，2 1 ( q + 1 ) 2 ) 。 举个具体的例子，假设物理页大小为4 k b ，每个索引记录大小为4 0 个字节， 则每一个物理页大约可以存放1 0 0 条索引记录即i t i = 1 0 0 。 如果有1 0 0 万个键值，用m = 1 0 0 的b + - t r e e 索引起来，则 1 0 9 d o o 2 ( ( 1 0 0 0 0 0 0 + 1 ) 2 ) = 5 层， 如果根节点常驻内存，则通常单值查找只需 要读四个索引块( 物理页) 即可。由此可以看到b + - t r e e 在减少磁盘存取方面的 作用。 b + - t r e e 因为每个节点内的值序列是有序的，故节点内一般采用二分查找。 b + - t r e e 节点的插入和删除较为复杂，因为删除后涉及到保持b + - t r e e 的平衡 等，需要分裂或合并一些节点，即重新组织b + - t r e e ，这些内容就不在这里详细 介绍了。有兴趣的读者可以查阅有关数据结构方面的资料。 b + - t r e e 是数据库系统中最普遍的数据结构，很少需要重新组织，并且能够 很好地支持多种查询类型，如点查询、范围查询和极值查询。比如用b + - t r e e 进 行范围查询( 区域查询) 。范围查询即是给出一个值的区间 x ，y 】，搜索索引值在 这个区间内的所有记录。对于这种范围查找，b + - t r e e 只需要先找到x 在叶节点 中的位置，再找到y 在叶节点中的记录，因为所有叶节点中的记录是有序的，所 以只需顺着叶节点间的指针将所有x 到y 的记录都输出即可。 b + - t r e e 与b t r e e 结构相似，区别在于b t r e e 的内部节点也保留了该值物理 地址的指针，叶节点就没有存储所有的值( 一部分在内部节点上) ，这样虽然提 高了点查询的效率( 有时不用搜索到叶节点，直接在内部节点就匹配了) ，但是 范围查洵等的效率却降低了不少( 因为叶节点的链上没有包含全部的值) 。 总的说来，b + - t r e e 的优点是整个索引树结构层数很少( 是总记录数的对数 级) ，性能稳定( 单值查询最坏情况的i o 也为树高) 。且当更新记录时，有算法 能自动地进行小的、局部的重构，保持其平衡性。缺点是有额外的插入和删除的 负担，且有额外的存储开销。但由于其优点显著超过其缺点，故得b + - t r e e 被大 量应用于外存存储，当下所有的商用数据库，比如s q ls e r v e r 、d b 2 、o r a c l e 和s y b a s e 等等的主要索引结构都是基于b + - t r e e 的。 9 巾山大学博士学位论文 2 2 2h a s h 索引 哈希( h a s h ) 索引也是一种重要的索引结构，他具有显著的优点和缺点。图 3 3 是h a s h 索引的示意图。 码值h a s h 码值记录及地址 0 r 1 r 9 r h a s h 函数b l r 1 3 r 2 1 r 3 一l n r 7 4 图3 3h a s h 索引示意图 如图3 3 ，h a s h 结构是一种 值对的映射方法，它通过一种 称为哈希函数的伪随机函数，将不同的码值( 查找键的值) 以尽量相同的概率映 射到不同的函数值( 即是h a s h 码值) 上，函数值的分布类似随机函数，但对于 相同的码值，总是映射到相同的函数值上。哈希函数的返回值是一个地址( 指针) ， 该码值的相关记录索引项的信息就存储在这个地址里。 可以把哈希函数的值指向的地方看作是桶( b u c k e t ) ，然后将码值映射到相应 的桶，把此码值的信息装在桶内，如果一个桶装满了，则称之为溢出，这种情况 下可以重新申请一个新的桶，将前一个桶和新桶用指针连接起来( 称为溢出链) ， 然后继续在新桶里面装与此码值对应的记录，比如图3 2 中r 2 的桶就是连在溢 出链上的新桶。 哈希机构最大的优势在于点查询，不管什么码值，都几乎能在一次磁盘访问 中得到记录信息( 除了有溢出链，这种情况下就可能需要超过一次磁盘访问了) 。 如果哈希结构带有很大数目的溢出链时，就需要重新组织哈希结构。避免溢出链 的方法在于选取好的h a s h 函数和适度利用哈希空间，某些效率顾问建议哈希表 的使用不应超过5 0 ，即是指所有桶的平均利用率不应超过5 0 ，以保证尽量 少的溢出链。 也因为需要保证尽量少的溢出链，哈希结构具有相对差的空间利用率，且经 10 中山大学博士学位论文 常需要重构。但相对于大多数应用来说，数据量并不是非常大，因此是可以容忍 的。哈希结构对哈希函数的选择要求很高，要求将码值平均分开，对于不同分布 的索引码值需要不同的h a s h 函数，这就需要在应用初期就要预测数据的种类和 分布，或应用中对已有的h a s h 索引不断重构。 总的说来，哈希索引有相对较低的空间利用率，但对于点查询和多点查询有 非常好的执行效率，即i o 次数非常少( 几乎只有1 次i o ) ；但不适用于必须扫 描很多数据的查询，如极值查询和范围查询等。 2 2 3 位图索引 位图索引的应用也比较广。其主要思想就是对于需要索引的属性的所有值， 都选取具有几个位( 比如位图) 的一个矢量来表示，且每个位图的大小和被索引 的属性的数量相等。 位图索引对于那些属性值只有两个的情况下是最有效的，如性别( 男女) ， 婚否( 已婚未婚) ，判断( 是否) 等等，在这些应用里，位图索引作为掩码使用， 如图3 4 中，属性a 里取值有三种，优异、及格和不及格，而在属性b 中，性别取值只有两种，即：男和女。 优异 及格 不及格 男 女 属性a 位图 属性b 位图 l0l0 0000l0l0l0l 1l001 l00l0l olol l 1 l l0lolo1o 00l l00l l0l0 图3 4 位图索引示意图 也可以将位图矢量和取值范围联系起来，如对于一个身高属性，一个矢量可 以表示0 1 0 0 厘米，另一个矢量可以表示l o o 一1 2 0 厘米，等等。 因为有多少条记录，位图就有多少位( 如图3 4 ) ，所以当记录数目非常大时， l一000 一一00一o一o一0一0 一一oo一0100一lo 一一000一oolo一0一，一oo0 一，一o一0一o0 一l 一000一o 一一o00一l0 一l 一000一l0一o一10一olo一0一一0一oo 一一o一00 中山大学博士学位论文 位图也变得很耗费空间。虽然位图中有许多0 ，可以采用相应的压缩方法进行压 缩处理【1 5 】，但是此时每当添加记录、删除记录或修改记录的索引项的值，就必 须重新解压缩和修改，重新压缩位图，造成一系列多余的负担。故用不用压缩， 要以实际情况而定。应用位图最合适的地方是数据信息基本不会修改的地方，比 如数据仓库。 位图索引的优势是能够容易地使用多个位图来回答单一地查询。一个具有几 个谓词的查询，如果其中在多个谓词关联属性上面都建有位图索引，就可以对各 个相应位图进行操作，直接得到满足这几个谓词的结果记录。因为位图操作是位 操作，故在位图上的操作是十分快的。个属性的取值很少时适于用位图索引， 比如性别，只有男和女，如果在上面建立b + - t r e e 或h a s h 索引，查询时访问了 多个物理页，但最后还是只减少了一