搜索
数据仓库中的索引技术分析与研究【摘要】本文主要介绍了数据仓库的几种索引技术。一方面首先介绍了传统的索引技术，进而简要介绍了基于传统索引技术发展起来的索引技术。另一方面通过分析对比各个技术之间的优缺点和主要适用场合，以提供在数据仓库的实施中选择合适的索引技术的建议，提高系统性能，优化客户体验。【关键字】数据仓库索引技术优缺点适用场合优化变体【Abstract】ThispaperhasamajorintroductionaboutseveralindextechnologiesofDatawarehouse.Ontheonehand，youwillhaveafirstviewabouttraditionalindextechnology，andthenyouwillknowaboutsomedevelopingindextechnologiesinbrief.Ontheotherhand，itgivesyousomesuggestionswhenyouputyourdatawarehouseintoeffectthroughhavingacomparativeanalysisabouttheirmeritanddemeritandtheirmajorsuitablesituationamongthosetechnologies.Finally，itcanimproveyousystemperformanceandoptimizethecustomers’experience.【Keyword】Datewarehouse，indextechnology，meritanddemerit，suitablesituation，optimizationandpromotion目录1、引言..........................................................................................................................32、数据仓库索引技术概述..........................................................................................32.1、概念...............................................................................................................32.2、分类...............................................................................................................32.3、简要介绍.......................................................................................................33、数据仓库索引技术精细介绍..................................................................................43.1、树形索引.......................................................................................................43.1.2、B-树索引............................................................................................43.1.2、R-树索引............................................................................................43.1.3、四叉树索引和QR-树索引................................................................43.2、位图索引.......................................................................................................53.2.1、简单位图索引....................................................................................53.2.2、优化位图索引....................................................................................53.3、连接索引.......................................................................................................63.4、散列索引.......................................................................................................63.5、倒排索引.......................................................................................................63.6、基于多维数组索引.......................................................................................63.7、反转索引.......................................................................................................73.8、网格文件.......................................................................................................74、论文总结..................................................................................................................71、引言随着计算机技术的不断应用和提高，基于数据挖掘的多功能应用已经不只是停留在高层次、高科技的军用、政府机关和商家，它已然深入到社会生活的各个角落。比如基于数据仓库和数据挖掘对保险公司、金融机构甚至超市卖场、高考志愿进行的数据分析以提供决策支持。随着数据仓库的广泛应用，怎样从庞大的数据仓库字典中迅速检索到我们需要的数据或对查询进行优化成了国内外众多学者竞相研究的课题。目前，数据仓库中查询优化技术主要有索引技术、视图分割和OLAP并行查询。其中数据仓库索引技术是基于传统数据库索引技术发展起来的，通过在数据仓库中对维表增加索引，进而提高数据的检索速度，改善数据查询性能，加强维表之间的连接，特别是在实现数据的参考完整性方面有重要意义，另外也可以在查询的过程中，使用优化器，以提高系统性能。2、数据仓库索引技术概述2.1、概念数据仓库索引是一个单独的、物理的数据结构，它是某个表中一列或若干列值的集合与相应的指向表中物理标识这些值的数据页的逻辑指针清单。数据仓库的索引技术是基于数据库的索引技术发展起来的对数据仓库中的数据查询优化的技术。2.2、分类按存储结构不同可分为：唯一性索引、聚簇索引和非聚簇索引；按组织形式不同可分为：线性索引、静态索引、倒排索引和动态索引等。2.3、简要介绍目前，数据仓库常用的索引技术有树形索引、位图索引、连接索引、散列（哈希）表索引和倒排索引，其中树形索引可分为B-树、B+树、B*树、-R树等；位图索引可分为基本位图索引和编码位图索引，并在此基础上有分层位图索引、区域位图索引、分段位图索引。连接索引可实现多表连接，基于此还有位图连接索引。散列索引又有其变种可扩张散列表和网格文件。另外基于传统索引技术还有其它的索引方法如基于多维数组的索引和网格文件等。3、数据仓库索引技术精细介绍3.1、树形索引数据仓库树形索引结构主要有B-树索引、-R树索引、四叉树索引、QR-树索引等，树形索引结构适用于高基数维属性，目前这类索引树结构已超过50种。3.1.2、B-树索引B-树索引是传统平衡树。可以在一个属性上建立索引也可建立多个属性上的索引，以用于多个属性上的查询，但需要建立属性个数为指数级的B-树数目。适用范围：适用于对高基数的列值进行检索，普遍应用于各种编码的索引，例如产品编码、客户编码等，也适用于多列值的索引。适用于不断插入、更新和删除的表。优化及变体：B+树是B-树的一种变体，B+树与B-树相同，也是一种多路搜索树，具有较高的存取效率。B*树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟的指针。3.1.2、R-树索引R-树索引基于传统B-树索引技术而发展起来的面向多维空间对象的索引结构，采用最小矩形来递归分解索引空间，效率较B-树高。优点：结构简单、易于维护及适用范围广等。缺点：由于该索引结构基于所有维建立，故不能很好地满足基于部分维查询的需要，另外，由于其中间节点的矩形区域之间不可避免地会产生重叠，因此区域搜索必须沿着多条查找路径进行，可能导致查询路径失效，从而影响查询性能，尤其是当失败路径较长时，这种影响会更加严重。其查找性能随空间数据量的增加急剧下降。适合范围：适合于对动态数据的查询操作，适用OLAP数据的多维性质。多维数据的组织方式中的方体树，就是R-树在多维数据中的一个应用。优化及变体：由基本的R-树出现了很多变体：*R树、K-D树、+R树、F树、SR树等。-R树优化就是尽可能减少子空间的重叠，即增加子空间中数据的聚集性，减少各子空间之间数据的相关性。3.1.3、四叉树索引和QR-树索引四叉树索引是用超平面的方法来组织索引结构的多维索引，它将索引空间划分为多个搜索子空间，搜索时可按照递归分解的办法，逐级搜索各个子空间的索引来查找结果。但该索引不是平衡树，它采用线性的存储结构，数据密集的地方树的深度较高。优点是：多维对象查询速度快，插入和删除操作简单方便。QR-树索引是数据仓库里引用了空间索引树形结构的一种新型多维索引，结合四叉树和R-树的各自优点，在进行查找时，将查找空间限制在整个索引空间的某一个部分，采用四叉树的索引来完成，而对于每一个子索引空间的数据，采用-R树的索引来组织数据，这样既可以满足较高的存储效率，又可以避免太多的无效查找，提高查找性能。3.2、位图索引位图索引是另外一种比较重要的数据仓库索引技术，主要基于二进制逻辑运算使各种比较、连接、和聚集操作都转换为位算术运算以简化操作来达到查询优化的目的。当维基数较低、查询范围较模糊或数据较为稀疏难以找到密集区域时，采用树索引很难取得较好的查询效率时，可采用位图索引。3.2.1、简单位图索引“位”是位图索引的核心，每一位与索引可能的取值之一相对应。在索引列的可能取值比较少时，位图索引可节省空间，因为只要4位即可，与之相比，B-树则要32位（即4个字节）。优点：节省空间和CPU，查询效率高，实现简单，具有很强的可操作性。缺点：当索引列取值较多时，尤其当字段数有许多不同值时，该索引需要太多空间。位图索引的另一个缺陷是锁（页锁