在数据仓库和商业智能(BI)解决方案中加快查询处理是一个急需解决的问题。使用汇总表或索引等机制可以有效提高查询速度，其中预定义查询的汇总表已具有较好的性能，但需要预先花费额外的执行时间，而索引是一个更加高性能的且无需额外硬件的解决方案，但其中面临的挑战是如何找到一个合适各种数据集且都保持较高性能的索引类型。　　低基数数据在数据仓库中应用广泛，基数是一个数据集的列中值的个数。一般有大量重复值的列称作为低基数列，例如性别列，一般只有两个值:男性和女性，当然可以用其它的2个不同的符号来表示。　　B树是存储排序数据并允许以O(logn)的运行时间进行查找的树形数据结构，但B树索引应用于低基数值列时是一个非常低效的索引方法，在进行即席查询且数据量大时需要非常多I/O操作。因此一些关系型数据库管理系统采用新的索引技术，如位图索引，用以加快查询处理。　　位图索引有一个用于快速数据检索的特定结构，主要是利用二进制数（0或1）的字符串，以指示一个表中被索引的列是否为一个特定的值，也就是说，如果在一个索引列中一个特定的值存在，位图索引设置为‘1，否则为‘0。与其它的索引技术相比，位图索引能大幅减少空间的使用，对于复杂逻辑的选择操作，可通过执行位的运算“AND”，“OR”，“NOT”等来快速地完成。位图索引的应用非常广泛，主要用于数据仓库系统和大型科学数据库。通过执行跨列位图间的快速逻辑运算，位图索引提供了一个更快的查询解决，而且能被被当代硬件广泛支持。　　很多商业的数据库系统都采用位图索引，如Oracle，从1995年开始就提供了位图索引，其它主要系统如DB2和Microsoft SQL Server没有采用。Microsoft SQL Server可能通过哈希连接生成位图，但不是通用的索引。DB2已经采用编码矢量索引，但是这基本上是一个编码投影索引，而不是一个位图索引。　　本论文的目的是通过实验的方式来证明在数据仓库中位图索引比B树索引更有效，尤其是对于低基数值列。在Oracle环境中，B树索引一般为默认的索引方式。我们通过3个典型的实验来测试在两个索引方式下复杂查询的执行时间，在每一个实验中我们分别测试3个条件、2个条件与1个条件的查询，并且测试4个不同的数据集，分别有100万条、80万条、60万条、30万条记录。　　我们首先在Oracle环境下设计并实现图形用户界面，采用Oracle Developer6i工具套件，这个套件由许多用于开发和编程项目的软件组成，这些软件以可视化的方式来处理数据仓库并操纵数据库。这意味着，使用可视化编程组件，如按钮、列表、标签、文本框、鼠标移动等等，无需复杂编程即可编写查询并以图形界面的方式呈现结果。我们使用Oracle10g的数据库来创建表和索引。　　我们设计与实现的界面有2个主要部分即搜索使用位图索引、搜索使用B树索引，这2个部分具有相同的查询语句与数据集。我们在查询项目中的选择的参数选项有地区、学院、性别和年龄。当要执行查询时，我们首先确定搜索选项，即相当于在SQL语中复杂的“Where子句”条件，每个选项所代表的组合列表是通过鼠标左键点击下拉列表选择值进行组合。在每次实验中，我们对位图索引与B树索引的查询响应时间进行详细记录与比对，从而揭示在不同数据集与不同列值情形下两个索引方法的性能差别。　　实验主要包含以下三个方案:　　方案一:搜索表使用三个条件，其中有两个AND运算操作。搜索上分别做4组记录，30万条、60万条、80万条与100万条记录。　　方案二:搜索表使用两个条件，即一个AND运算操作，搜索上分别进行4组记录，30万条、60万条、80万条与100万条记录。　　方案三:搜索表使用一个条件，搜索记录4组，分别30万条、60万条、80万条与100万条记录。　　我们用许多不同的查询参数来测试不同SQL查询以获得更多的结果进行较为全面的分析。从三个实验方案进行观察发现，位图索引在对于低基数值列如“Y”或“N”、“男”或“女”等比B树索引速度优势明显。但是位图索引只是方便静态表（无更新）的查询，如果查询的表不是只读的，则B树索引是一种相对有效的选择。位图索引对于决策支持系统、数据仓库、OLAP等数据相对静态的情形非常有效，而B树索引则对于OLTP环境更有效。已有相关研究将位图索引和B树索引的时间和空间复杂性计算规则进行了分析，数学计算表明位图索引的时间和空间复杂性比B树索引低，尤其是对于低基数值列。　　对于大型数据仓库来说，位图索引被认为是在当前和未来很有发展前途的索引，因此我们期待提出更有效的位图索引方法。我们的目标是通过采取新的方法来提高位图索引的性能，这个方法的主要思想是将基本的位图索引算法和基于值域编码算法进行有效结合，考虑不同的基数值列类型。　　在基于值域编码算法（是基本的位图索引算法的改进）中，位图矢量用于表示一定范围内的值，而不是一个单独的值。查询处理器读取该位图矢量中的对象，并删除那些超出目标范围的对象。此方法的主要优势是提高了位图索引性能的效率，通过减少位图矢量所需的扫描时间，特别是当我们处理一定范围内值的时候，通过将值域分割成更小的域用以显著减少存储开销。基本的位图索引的想法是使用一个字符串的比特0或1，以指示是否一个元组的属性值为某一个特定值，其主要优势是逻辑运算能很好的被硬件支持，操作的执行都相当快。而且，用于构造位图索引的成本及其根据位图进行查找的成本都非常低。然而，简单的位图索引只对具有低数量不同值的属性才有效，因为，如果索引的属性的基数值低，则需要一个较小的数字位图，索引结构的空间复杂度低，而对于高基数值属性，则需要一个很大的数字位图，索引结构的空间复杂度高、时间性能也低，这成为基本位置索引算法的明显缺陷。　　我们通过观察发现，基于值域编码算法由于可以将某一范围数值归类到某一个值，对于高基数值属性，可以处理成相对规模较小的数字位图，从而可以克服基本索引算法的缺陷。因此我们提出把基于值域编码算法和基本位图索引算法进行有效结合，通过引进相异值比率参数并对列进行自动计算，在相异值比率较高即不同的值多称之为高基数值属性时采用基于值域编码算法，当相异值比率低即称之为低基数值属性时采用基本位置索引，如果相异值比率超过一定值时，则采用B树索引。　　通过引入数学方程式并使用二项式概率分布规则，我们对提出的混合索引方法的时间复杂性进行了分析，结果表明新方法的时间复杂性将低于单独使用基本位图算法，在最坏的情况下将和基于值域编码算法的时间复杂度相同。　　本论文包含五个章节，第一章叙述位图索引的引言和相关工作。在第二章中，我们提出了B树索引和位图索引的概述和一些相关的索引技术及各个索引的优势和劣势。在第三章中，我们阐述了oracle developer的方法和关键技术和SQL数据库中创建表和索引的过程，在第四章中，我们描述了三个实验的实施完成，并阐明结果的讨论和每个索引的时间和空间复杂度，由于我们提出把基本位图索引与基于编码的范围结合起来的方法，最终提高了位图索引的效率。第五章介绍了结论和未来的工作。