（计算机软件与理论专业论文）数据仓库中基于位图索引查询优化的研究.pdf

原创性声明 li i l l l ltl1 1 1 1 1 1 1i iii i ii iiiii y 18 3 3 8 5 6 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：手呈吨 日期：刀fd 年箩月弓f e l 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 学位论文作者：平呈司毛日期：加f 。年罗月弓日 摘要 摘要 索引是数据仓库查询优化的重要技术，主要包括树形索引和位图索引。其 中位图索引因为其结构简单，并且硬件支持二进制位运算效率很高，被广泛应 用在数据仓库中。在属性的基数( 该属性可能的取值数) 低的情况下，位图索 引已经被证明是十分高效的。但在基数比较高的情况下，位图索引需要占用大 量的存储空间。位图索引往往被认为只有在属性基数较低情况下才适合使用。 为了克服这个难题，现今研究者们已经提出了很多方法，包括编码，压缩， b i n 。其中b i n 位图索引可以有效的降低高基数时位图占用的空间。这种索引不 像简单位图索引那样建立在每一个不同的属性值上，而是建立在一个个的属性 范围上。但它同时也带来了另一个难题，就是候选检查。候选检查往往占用大 部分的查询时间。 采用传统多维查询算法，对各属性进行查询的顺序不同，可能对总候选检 查数目产生重大影响。本文给出两个定理，证明了影响排序的两个因素。并据 此提出一种基于权值排序算法，通过在执行查询前对各属性查询进行排序，使 总的候选检查的数目尽可能少。理论分析和实验表明，此排序算法可以明显减 少总候选检查数目，优化了传统多维查询算法。 但是排序的传统多维查询算法并不能减少查询的第一维所需的候选检查数 目，实验表明第一维所需的候选检查数目往往占总候选检查数目的大部。通过 预扫描( 推迟候选检查) 可以有效解决这个问题，但是进行预扫描需要额外的花 费，即要扫描更多的索引，这个代价是不能忽视的。考虑到预扫描一定维数后， 继续预扫描将不会明显的减少总的候选检查数目，本文在排序的基础上提出动 态预扫描算法，目标是在预扫描属性数目和总的候选检查数目中找出一个合理 的平衡点，以提高查询效率。理论分析和实验结果表明，动态预扫描算法取得 了良好的效果。 关键字：数据仓库位图索引b i n n i n g 编码压缩多维查询 a b s t r a c t i n d e xi sa ni m p o r t a n tq u e r yo p t i m i z a t i o nt e c h n i q u ef o rd a t aw a r e h o u s e , w h i c h i n c l u d i n gt r e ei n d e x e sa n db i t m a pi n d e x e s b i t m a pi n d e xi sw i d e l yu s e di nt h ed a t a w a r e h o u s eb e c a u s eo fi t ss i m p l es t r u c t u r ea n di t sh i g he f f i c i e n c yo fl o g i co p e r a t i o n b i t m a pi n d e xh a sp r o v e nt ob ev e r ye f f i c i e n tw i n ll o wa t t r i b u t ec a r d i n a l i t i e s ( t h e n u m b e ro fd i s t i n c tv a l u e s ) h o w e v e r , f o rh i g h - c a r d i n a l i t ya t t r i b u t e s ，b i t m a pi n d e x r e q u i r e st o om u c hs t o r a g e t h e r e f o r e , b i t m a pi n d e xi so f t e nt h i n kt ob eu n s u i t a b l ef o r h i g h - c a r d i n a l i t ya t t r i b u t e s r e s e a r c h e r sh a v ep r o v i d e dal o to fs t r a t e g i e st os o l v et h i sp r o b l e m ，i n c l u d i n g c o d i n g , c o m p r e s s i o n ，b i n b i t m a pi n d e x 谢t l lb i nc a ne f f e c t i v e l yr e d u c et h es t o r a g e r e q u i r e do nh i g h - c a r d i n a l i t ya t t r i b u t e s t h i st e c h n i q u eb u i l t ab i t m a pf o re a c h b i n ( a t t r i b u t er a n g e ) r a t h e rt h a nd i s t i n c tv a l u e s b u t i ta l s oi n t r o d u c e sa n o t h e r p r o b l e m ，w h i c hi sc a l l e dc a n d i d a t ec h e c k c a n d i d a t ec h e c ku s u a l l yd o m i n a t e st h et o t a l q u e r yp r o c e s s i n gt i m e u s i n gt r a d i t i o n a lm u l t i d i m e n s i o n a lq u e r ya l g o r i t h m ，q u e r yt h ev a r i o u sa t t r i b u t e s o fad i f f e r e n to r d e r , w i l lb es i g n i f i c a n t l ya f f e c t e dt h et o t a ln u m b e ro fc a n d i d a t ec h e c k t h i sp a p e rp r e s e n t st w ot h e o r e m s ，w h i c hp r o v et h a tt w of a c t o r sa f f e c tt h es o r t i n g 1 a n d a c c o r d i n g l y , w ep r e s e n t sad y n a m i cs o r t i n ga l g o r i t h mt oi m p r o v eq u e r yp e r f o r m a n c e t h ea l g o r i t h mt h r o u g hs o r t i n gt h ea t t r i b u t e st or e d u c et h en u m b e ro fc a n d i d a t ec h e c k t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o wt h a tt h i ss o r t i n ga l g o r i t h mc a n s i g n i f i c a n t l yr e d u c et h et o t a ln u m b e ro f c a n d i d a t ec h e c k ，a n do p t i m i z e dt h et r a d i t i o n a l m u l t i d i m e n s i o n a lq u e r ya l g o r i t h m b u tt h ed y n a m i cs o r t i n ga l g o r i t h mc a nn o tr e d u c et h en u m b e ro fc a n d i d a t ec h e c k n e e d e do ft h ef i r s td i m e n s i o n e x p e r i m e n t ss h o wt h a ti ta l w a y so v e rt h eh a l fo ft o t a l n u m b e ro fc a n d i d a t ec h e c k t h en u m b e ro fc a n d i d a t ec h e c kc a nb ee f f e c t i v e l yr e d u c e d b yt h ep r e - s c a n ( d e l a y e dc a n d i d a t ec h e c k ) b u tt h ep r c - s c a n n i n gr e q u i r e sa d d i t i o n a l c o s t ，i tr e q u i r e sm o r eo p e r a t i o n so nb i t m a p s a n dt h ec o s tc a nn o tb ei g n o r e d t a k i n g i n t oa c c o u n ta f t e rac e r t a i nd i m e n s i o n s ，t os t i l lp r e - s c a nw i l ln o ts i g n i f i c a n t l yr e d u c e t h et o t a ln u m b e ro fc a n d i d a t ec h e c k t h ep a p e rp r o p o s ead y n a m i cp r e - s c a na l g o r i t h m l l t od e t e r m i n ew h a tn u m b e ro fa t t r i b u t e sa n dw h i c ha t t r i b u t e ss h o u l db ep r e - s c a n d y n a m i c a l l yt oi m p r o v eq u e r ye f f i c i e n c y t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a l r e s u l t ss h o wt h a td y n a m i ci n e - s c a na l g o r i t h m sw o r k e dw e l l k e y w o r d s ：d a t aw a r e h o u s e ；b i t m a pi n d e x ；b i n n i n g ；m u l t i - d i m e n s i o n a lq u e r i e s ； e n c o d i n g ；c o m p r e s s i o n i l i 目录 目录 摘要i a b s t r a c t i i 目录i v 1 绪论l 1 1 研究课题背景及意义1 1 2 国内外研究现状l 1 3 本文结构安排3 2 数据仓库基础及常用索引技术4 2 1 数据仓库概述4 2 1 1 数据仓库的概念4 2 1 2 操作数据库系统与数据仓库的区别4 2 2 数据仓库的多维数据模型5 2 2 1 星型模型5 2 2 2 雪花模型6 2 3 数据仓库的常用索引7 2 3 1b _ 树索引7 2 3 2r 一树索弓i 8 2 3 3 位图索引9 3 基于权值排序的查询优化算法1 8 3 1b i n 位图索引1 8 3 2 基于b i n 位图索引的一维查询1 9 3 3 基于b i n 位图索引的多维查询，2 1 i v 目录 3 3 1 基于b i n 位图索引多维查询算法2 2 3 3 2 基于权值排序优化算法2 3 3 4 实验结果与分析2 5 3 4 1 实验数据2 5 3 4 2 实验设计及结果分析2 6 4 基于动态预扫描的查询优化算法，2 9 4 1 范围编码的b i n 位图索引2 9 4 2 基于范围编码b i n 位图索引的一维查询3 0 4 3 基于范围编码b i n 位图索引的多维查询3 0 4 3 1 预扫描算法3 1 4 3 2 基于排序的预扫描优化算法3 1 4 3 3 基于动态预扫描的优化算法3 2 4 4 实验结果与分析3 5 4 4 1 实验数据3 5 4 4 2 实验设计及结果分析3 5 5 总结与展望3 8 5 1 本文总结3 8 5 2 展望3 8 参考文献4 0 个人简历在学期间发表的学术论文与研究成果4 3 个人简历4 3 攻读硕士学位期间发表的学术论文4 3 致谢4 4 v l 绪论 1 绪论 1 1 研究课题背景及意义 随着计算机的广泛应用，计算机里存储的包含企业信息的数据也越来越多。 如果可以从这些类型繁多、来源复杂的巨量数据中得到有用的决策信息，使管 理者能及时正确的决策，将会巨大促进企业的发展。数据仓库( d a t a w a r e h o u e s ) 就是应这种需求而生的。使用数据仓库的目的就是从巨量的历史数据中提取出 有用的信息，给企业的管理者提供决策支持。 由于数据仓库中数据量大而且查询复杂，响应用户的查询往往是十分耗时 的。因此查询优化成为影响数据仓库应用的重要因素。国内外提出很多查询优 化技术，其中索引是关键。使用恰当的索引可以有效的提高查询效率。由于数 据仓库具有多维性质，使得现今大多关系型数据库所采用的b 一树索引并不适合。 位图索引因为适合数据仓库的特性，在数据仓库中得到广泛应用。 在属性基数( 该属性可能的取值数) 较低的情况，位图索引非常高效。而 在基数较高的情况，位图索引通常因为占用太多存储空间被认为不适用。现实 中有些数据特别是科学数据中某些属性的基数非常大，可以达到几百万，若采 用传统位图索引技术，需要建立几百万个位图，这在空间上是不可能的。要在 高基数情况下使用位图索引，必须采用新的技术减少索引占用的空间，而且要 保证查询效率。数据仓库中的数据维数也可能较高，可以达到几十维。这些维 中并没有哪一个属性可以起主导作用，也就是说无论在哪一个属性上单独建立 索引都不能明显的提高查询效率。这种情况可以排除使用b 一树索引，因其多维 协同性太差。如何在高基数的情况下有效的使用位图索引是现今一个研究的热 点。 1 2 国内外研究现状 数据仓库作为新兴的技术，近年来得到越来越广泛的应用。现今的数据仓 库往往建立在传统的操作型数据库基础之上，而传统数据库大多采用b 一树索引， 这使得尽管b 一树索引不太适合数据仓库，但仍被大量使用。位图索引因为其技 术优势，以及随着对其研究的深入，如今主要的数据库厂商，如i b m ，o r a c l e 等， 1 绪论 都在各自的产品中实现了位图索引。 位图索引在高基数情况下占用太多存储空间，严重限制着位图索引的应用。 近年来研究者已经提出了不少方法以使位图索引在高基数的情况下也高效。这 些方法可以分为3 类，即编码、压缩以及分箱( b i n n i n g ) 。这3 类方法各有其优 缺点，任何一种单独使用都不能取得令人满意的效果。国外对这些方法进行了 研究和改进，并且进行了组合研究。 k e s h e n gw u 等提出一种新的压缩方法w o r d - a l ig n e dh y b r id ( w a h ) i l 】，这是 一种基于字的编码方法。它考虑到现今计算机每次存取一个字长的数据，相比 之前常用的压缩方法b y t e a lig n e db it m a pc o d e ( b b c ) 【2 】( 基于字节的) ，虽然 要多占用约5 0 9 6 的存储空间( 基于字节的压缩方法对至少连续7 个值相同的数据 就可以压缩，而基于字长的则至少需要3 1 个连续相同的) ，但响应时间却比b b c 快1 2 倍，近年来得到了广泛的应用。 d o r o nr o t e 埴n 等在【3 ，4 】中考虑到在已知工作量下，b i n 边界对总的候选检查数 目产生重要影响。文中提出动态确定b i n 边界的的方法，并从一维扩展的多维。 文中证明b i n 边界只有从查询集的查询边界中取值才能得到最优解，相比从所有 属性值中取值，求得最优边界的效率要高很多。文中给出一个公式评价不同分 区边界时的i 0 花费，并给出确定最优边界的方法。这种方法的缺点是只适用于 已知工作量的情况，但在实际中大多数情况是不满足的。 r i s h ir a k e s hs i n h a 等在文【5 】中提出了分层的b i n 位图索引方法。文中研究 了科学数据的特性，证明了在属性基数非常大的情况，采用压缩和i n t e r v a l 编 码甚至二进制编码也会占用太大的空间而不可用。文中还讨论了怎样分层以及 分几层可以使查询效率更高。分层的方法确实可以提高查询效率，但是它需要 更多的存储空间。 r i s h ir a k e s hs i n h a l 等在文【6 】中针对科学数据存储紧张的情况，对分层的 b i n 方法进行改进，利用【3 ，4 】提出的动态分区方法，用快速启发函数确定分区的边 界。该文的方法对分层b i n 方法和压缩进行了结合，压缩方法用的是 w o r d - a l i g n e dh y b r i d ( w a h ) 。 n i w a nw a t t 锄出仇：m 鲥等提出一种新的位图编码方澍1 刀，在位图索引占用 空间上要优于i n t e r v a l 编码，并且验证了对等值查询和成员查询是高效的，但 是并未对范围查询进行研究。 k u r ts t o c l ( i n g e f 等在文中1 8 】针对基于b i n 的位图索引，对多维情况的查询方法 2 l 绪论 进行了研究。文中提出一种新的多维查询算法，并与其它两种查询算法进行了 对比研究。研究表明其中新算法是有效的，在某些情况查询效率要比其它算法 高很多。但是因为新算法需要额外扫描位图，通常情况下和第二种方法效率相 当。 国内对位图索引的研究主要集中到位图的编码上。胡孔法等提出一种基于 维层次编码的位图索引方法1 9 1 ，在维具有层次性时，使用这种索引方法可以有效 的减少索引占用的空间，取得良好的查询性能。这种方法可以提高0 l a p 查询效 率，查询算法参见文【l o l 。这种方法的优点是考虑了维的层次特性，但并非所有 维都具有层次性。 众所周知，数据仓库中多表连接是比较耗时的，文 1 1 , 1 2 l 对多表连接算法进行 了研究。 1 3 本文结构安排 第l 章为绪论，介绍了研究课题的背景及意义，介绍了国内外研究现状， 并给出了本文的组织结构安排。 第2 章介绍了数据仓库的概念及数据模型。并介绍了数据仓库中常用的索 引技术及各自的优缺点。 第3 章介绍基于b i n 位图索引的多维基于权值排序算法。针对多维情况，对 各属性的查询顺序不同，会影响总的查询效率，提出基于权值排序算法。并给 出了理论分析和实验结果。 第4 章针对传统多维算法的缺点，提出动态预扫描算法。该算法的目标是 在预扫描属性数目和总的候选检查数目中找出一个合理的平衡点，以提高总的 查询效率。并给出理论分析实及验结果。 第5 章是总结与展望，对本文内容进行简要的总结，并对未来工作提出展 望。 3 2 数据仓库基础及常用索引技术 2 数据仓库基础及常用索引技术 2 1 数据仓库概述 2 1 1 数据仓库的概念 数据仓库并不是一种软件产品或应用程序，而是系统体系结构【1 3 】。上世纪 9 0 年代初，w h i n m o n 首次提出数据仓库的概念【l 哪：数据仓库是一个面向主题 的、集成的、时变的、相对稳定的数据集合，用来给管理人员提供决策支州1 5 , 1 6 。 数据仓库的四个特剧r 7 】： 1 面向主题的所谓主题，是指建立数据仓库进行决策时所关注的重点方 面，例如顾客情况，销售情况等。面向主题是指其数据是按照一定主题 组织的。而传统数据库的数据组织是围绕公司的应用，各个业务系统之 间相互分离。 2 集成的是指数据仓库中的数据是在对原有分散的、异构的复杂数据库 ， 数据进行提取、转换、加载，经过系统加工、汇总和整理得到的。数据 仓库中的数据必须是一致的全局信息。 3 时变的数据仓库中主要包含历史数据，它的数据是按不同时间段进行 组织的。数据仓库中的数据是反映历史变化的，通过对它分析可以对企 业的发展历程和未来趋势做出定量分析和预测。 4 相对稳定的是指数据进入数据仓库之后，一般会长期保留，不允许修 改和删除，只需定期的加载、刷新。传统数据库内的数据常常根据需要 进行实时更新。 2 1 2 操作数据库系统与数据仓库的区别 传统数据库已经被大家所熟知。通过和传统数据库的比较可以更容易理解 数据仓库的概念。两者的主要差别如下【1 7 , 1 8 ： 1 前者主要用于联机事务处理( o l t p ) ，后者主要用于联机分析处理 ( o l a p ) 。 2 前者是面向过程的，后者是面向主题的。 3 前者的数据是分散的、不同的，实时进行更新，后者的数据是集成的， 2 数据仓库基础及常用索引技术 往往是不能更改的。 4 从时间性上来说，前者是当前的，后者是历史的。 5 从结构上说，前者是关系型的，数据符合三级范式，后者是多维型的， 关系结构为星型雪花型或者混杂型。 6 前者的使用者主要为专业操作人员，后者多为管理人员，分析人员和决 策者。 2 2 数据仓库的多维数据模型 传统数据库常采用实体一关系数据模型，而数据仓库则不同。数据仓库中应 用最广泛的数据模型是多维模型。所谓维是一个组织要记录的透视图或实体。 例如一家连锁超市要记录它的销售情况，包含的维有时间，地点，商品，分店 等。每个维都有一个表与之相对应，这个表被称为维表。维表是用来进一步描 述维的，包括维的层次、成员类别等信息。例如地点维可以包含国家，省，城 市等属性。 多维数据模型十分重要，直接影响着数据库的设计，前端工具和o l a p 查询 引擎。多维数据模型是一个逻辑概念，在物理存储上可以有不同的实现。现如 今主要的多维数据模型包括星型模型、雪花模型、事实星座形模型等。 2 2 1 星型模型 数据仓库中使用最广泛的多维数据模型是星型模型【1 7 l 羽。这种模型主要包括 两类表：( 1 ) 事实表，包含着大量数据且没有冗余的中心表，存储了数据和维 标识符；( 2 ) 维表，每维对应一个。这种模型事实表通过维表外键和维表建立 联系，它的模型图像星星形状。其中维表在以事实表为中心的星星的射线上。 如图2 1 是一个典型的星型模型图。事实表销售通过维表外键和四个维商 品，分店，时间和地点建立联系。每个维对应一个维表。其中销售量和销售金 额是两个度量。事实表往往很大，为了使其尽可能小，维标识符( 如商品号， 分店号) 常常是系统产生的。 5 2 数据仓库基础及常用索引技术 图2 1 星型模型示例 因为星型模型中限制每个维只用一个维表表示，这使得维表可能是非规范 化的，所以存在数据冗余问题。另外，维表中的属性可能存在层次性。并且这 种模型不能解决业务更新时需要增加新维的问题【1 9 1 。 2 2 2 雪花模型 雪花模型1 7 , 1 s 是星型模式的变种，它不再限制每个维只用一个表表示。它把 一些星型模式中的维表规范化，因而一些数据被进一步分解的附加表中。 如图2 2 是一个典型的雪花模型图。和星型模式相比，原来的商品维表和 地点维表分别被规范化，生成新的商品维表和供应商表，地点维表和城市表。 图2 2 雪花模型示例 6 2 数据仓库基础及常用索引技术 和星型模型相比，雪花模型通过规范化维表减少了数据冗余。这种表优点 是节省了存储空间，并且容易维护。但是数据仓库中占用主要存储空间的是事 实表，和事实表相比，维表只占用少量空间。那么对维表空间的优化就显得微 不足道。此外雪花模型增加了表的数量，使得查询时需要更多的连接操作，而 连接操作是十分耗时，这种模型可能会降低数据仓库查询的性能。并且雪花模 型增加了用户处理表的数量，使查询操作复杂化，降低了系统的专用程度【2 0 】。 所以尽管雪花模式减少了数据冗余，但是并没有星型模式使用广泛。 2 3 数据仓库的常用索引 数据库系统中使用索引的目的是让用户查询更方便快捷。如果没有创建索 引，数据库中要查询某条记录，可能需要顺序扫描全表。通常，查询有索引的 表比查询没有索引的表要高效得多。原因是索引本身往往要比它所指向的记录 小，在相同存储空间上可以存放多得多的索引项。用户根据索引指向的地址查 找需要的内容，甚至对于有些查询只需要查询索引就可以。这意味着查询时需 要少得多的i o 量，大大提高查询的效率。数据仓库中的查询往往是复杂的多 维查询，涉及巨量数据，因此索引显得格外的重要。 根据其特性，数据仓库对索引的要求和传统数据库系统有所不同。数据仓 库查询的多维性，要求索引的协同性要好；数据仓库中数据量很大，对索引在 时空上的性能要求更高；数据仓库中的数据往往是只读的，相对稳定的( 定期 批量更新) ，对索引的更新性能要求不像传统数据库那么高。下面介绍一些数 据仓库中常用的索引技术。 2 3 1b 树索引 b 树作为最常见的一种索引，被现如今大多数的关系型数据库系统所采用。 b 一树的b ”表示的并不是b i n a r y ( 二叉) ，而是表示b a l a n c e d ( 平衡) 。它的定义如 - - k 2 1 , 2 2 , 2 3 m 序b 树：m 序b 一树是一棵m 叉搜索树，如果b 树非空，那么相应的扩充 树应满足以下特征： 1 根结点至少有2 个孩子。 2 除了根结点以外，所有内部结点至少有im 21 个孩子。 7 2 数据仓库基础及常用索引技术 3 所有外部结点位于同一层上。 容易看出，b 一树属于多叉平衡树。酽树中所有叶子结点都位于同一层( 最 底层) ，其中包含各个索引键以及其r o w i d ( 用来指向索引行) 。叶子结点之上的结 点用于在结构中实现导航。 在多属性的情况下，也可以创建b 一树索引进行多维查询。其缺点是只能按 建索引的属性顺序的前缀进行查询。比如有三个属性a l ，a 2 ，a 3 ，按其下标顺 序建立b - 树索引，那么在查找时可以用到此索引的情况是有3 种，即要查询的 属性为：a i a 2 a 3 ，a l a 2 ，或a l 。在其它情况下并不能用此索引来提高查询效率。 在o l a p 中，建立索引之前往往不能确定要查询的是何属性或其何种组合。虽然 可以对每种情况都建立相应的b 一树索引，但在属性多的情况下花费会很大。所 以b 一树索引并不是很适合于数据仓库。 b 一树索引的优点是结构简单、容易维护，另外现今大多关系型数据库系统 都采用这种索引技术，拥有较好的基础。从建立了b 一树索引的表中取数据的速 度和该表的大小关系不大。b - 树索引比较适合于插入、更新、删除操作频繁的 表。 2 3 2r - 树索引 r 一树最早由a g u t t m a n 2 4 提出，它是从b 一树扩展而来。r 一树也属于树形索 引结构，是面向多维空间对象的，它克服了b 一树不适合o l a p 数据的多维性质。 与b 树相似，p 树包括叶子结点和非叶子结点。非叶子结点主要为了导航，包 含若干个( m b r ，p o i e n t e r - t o - c h i l d ) 。其中m b r 为一最小矩形，包含了其对应 的所有孩子。这里的最小矩形是广义的，在三维上就是长方体，以此类推。 p o i e n t e r - t o - c h i l d 表示指向其孩子的指针。叶子结点都在树的最后一层上， 其结构和非叶子结点类似，只不过p o i e n t e r t o - c h il d 换成了g e o o b j e c t i d 。 通过g e o o b j e c t - i d 可以得到相应多维数据的详细信息。 相比其它索引，r - 树的优点有f 2 5 l ： 1 按照多维数据结构组织，灵活性高，可调节性强。 2 从b 一树发展而来，可以很好的融合传统数据库。 3 无须预先知道整个多维对象所在的多维范围，就可以创建索引。 r 一树是根据所有维建立索引的，查询空间对象往往也和所有维相关，所以 r 一树可以很好的满足多维空间对象查询。但是o l a p 的多维数据和多维空间对象 并不相同。针对o l a p 多维数据的查询，常常并不涉及所有维，只是涉及各维的 8 2 数据仓库基础及常用索引技术 组合。这使得对多维数据使用r 一树索引仍存在不足。 2 3 3 位图索引 位图索引【2 6 ，2 刀的基本思想是，给定一表t ，有n 条记录r l ，r 2 ，r n ，a 表示 t 的一个属性，其值域为：( a 1 ，a 2 ，a m ) ，那么在属性a 上建立的位图索引由 o _ l 向量集 b l ，b 2 ，b m ) 组成。其中b i 相对于a i ，ls i m ，其长度为n 。如 果记录r j 在a 上的取值为a i ，那么b i 在与其相应的位置取值为l ，否则取0 。 如图2 3 所示，有一属性可能的取值有3 个，0 、2 、5 ，则它需要3 个位图 向量来表示，向量的长度为记录的个数。 025 园团矿 图2 3 简单位图索引示例 假定表t 有n 条记录，属性a 的基数( 该属性上不同取值的个数) 为c ，那么 在a 上建立的简单位图索引占用的字节数为c * n 8 。如果在a 上建立b 树索 引，那么占用的字节数为1 4 4 p n ( s m ) ，式中的p 表示数据页的大小，m 代表b 树索引的阶数。如果m 中的一种。类似的双边查询形如q ：( ao pv 1 ) l o p ( ao pv 2 ) ，其中 o p ，) ，l o p a n d ，o r 。 等值编码位图索引很适合于等值查询，只需要扫描一个位图。例如要查询q ： a = l ，只需要扫描属性值1 所对应的位图向量，其中l 对应的记录为符合查询的， 0 对应的记录则不符合查询。但它不太适合于范围编码，例如有一个属性a 的基 数为c ，不妨设值域为 1 ，2 ，c ) 。则对于单边查询q - a i ，l i c 2 时，就可以先查询不符合查询的，再 取反即可。在最坏情况下回答一范围查询需要扫描( 2 2 个位图。 3 范围编码( r a n g e e n c o d e db i t m a pi n d e x ) 考虑到等值编码并不适合于范围查询，研究者们又提出了范围编码。范围 编码位图索引【3 0 】与等值编码位图索引的不同在于比较方法不同。等值编码位图 索引用的比较方法是相等，而范围编码位图索引采用的比较方法是。也就是说 采用范围编码，相应记录的属性值小于等于位图向量相应的值时，对应位取1 ， 否则取0 。 图2 4 是采用了范围编码的例子。图中t 有7 条记录，属性a 可能的取值 数为5 ，值域为 o ，2 ，5 ，6 ，7 ) 。这种情况可以采用一对应表，用( 0 ，1 ，2 ，4 ) 表示属性a 的值域。在实际中有不少值并不是整数，而是字符串，也可以采用 这种方法使用位图索引。 2 数据仓库基础及常用索引技术 图2 4 范围编码位图索引示例 从图2 4 中可以看到，值“7 ( 值域中最大的那个) 对应的位图向量中的值 全为l ，在实际中这个位图常常省略。范围编码位图索引所需的位图数比该属性 的基数c 少1 ，比等值编码节省了一个位图。在基数高的情况，节省这点空间是 微不足道的。 范围编码很适合于单边查询，只需要扫描一个位图就可以。如图2 4 ，对于 单边查询q ：a 2 ，则只需要把“2 1 对应的位图向量取反即可。对于单边查 询q ：a - 2 ，“2 中为1 的位所对应的记录符合查询，反之不符合。单边查询 最多只需扫描一个位图就可以。对于双边查询和等值查询，范围编码位图索引 需要扫描2 个位图。例如q ：a = 3 ，可以等价表示为小于等于3 但不小于等于2 ， 用“3 对应的位图和“2 ”对应的位图的非进行与运算即可。 范围编码位图索引采用比较符，查询中用到的其它比较符都可以转换为s 比较符。转换规则如下： a=vc ，1 ( a v - 1 ) 八( a v ) a v 1 ( a v ) a v 营a v 1 a v 1 ( a v - 1 ) 假定在属性a 上建立的范围编码位图索引为( b o ，b l ，b c - 2 ) ，相对应于a 上的值( o ，l ，c 2 ) ，有以下规n - a = 0 ，b o a = c l 营 b c - 2 a = v 营1b l 八b v 铮b 、r 1ob v a v 车争1 b v 1 1 2 。田刚，田刨2门刚3门u4门u 2 数据仓库基础及常用索引技术 a v b 。 i asjc ，b job i i a j b ob i 其中0 v c 一1 ，0 i j c - l 。 通过以上等价规则，可以在范围编码位图索引上响应各种查询。对于等值 查询，范围编码要比等值编码多扫描一倍的索引，而在存储上相差不大。另外 等值编码位图索引压缩性能要更好。这两种编码各有其优势，具体选用哪种需 根据实际情况而定。 4 i n t e r v a l 编码 c h a n & l o a n n i d i s 对传统编码方法进行研究，在1 9 9 9 年发表的论文【3 1 】中提出 以下定理： 在c 5 时，范围编码位图索引对于等值查询是最优的 无论c 取任何值，范围编码位图索引对于单边查询是最优的。 无论c 取任何值，范围编码位图索引对双边查询都不是最优的。 无论c 取任何值，等值编码位图索引对等值查询都是最优的。 无论c 取任何值，等值编码位图索引对单边查询和双边查询都不是最优的。 假定编码方法e 对查询q 需要花费的时间为t ，空间占用为s ，则说编码 方法e 对查询q 最优是指不存在其它的位图编码：( 1 ) 所花费的时间小于等于 t ；( 2 ) 所花费的空间小于等于s ；( 3 ) 以上两条至少有一条等号不成立。这里 所说的时间花销是指响应查询q 所需要扫描的位图数目，存储空间是指创建索 引所需的总位图数。 因为等值编码和范围编码都不是最优的双边查询编码方法，文献【3 l 】提出了 i n t e r v a l 编码，主要针对双边查询，旨在从空间时间性能上取得更好的效果。 i n t e r v a l 编码与等值编码和范围编码不同，它的每一个位图对应的不是单个 属性值，而是对应着一个区间( i n t e r v a l ) 。假定属性a 的基数为c ，在其上建立的 i n t e r v a l 编码位图索引由r c 2 1 个位图 b o ，b l ，b m ) 组成，其中b i = i ，i 怕】， m = l c 2i 1 。b i 中的1 表示相应的记录值v 落在区间【i i