王书海， 刘桂兰， 綦朝晖

（1．石家庄铁道大学 信息科学与技术学院，河北 石家庄 050043；（2．河北省大型结构健康诊断与控制实验室，河北 石家庄 050043）

0 引言

数据量的快速增长对数据检索效率提出了新的挑战。索引被证明是用于提高数据检索效率的关键技术，而位图索引依据其独特的位向量编码方式，在数据检索中得到广泛使用。位图索引按其编码处理方式可分为简单位图索引和编码位图索引。

简单位图索引依据其简单的编码方式即位向量，使其可以充分利用计算机逻辑运算的能力。简单位图索引中属性值的编码位数和属性基数有直接的关系，存储空间和查询时间都与基数成正比［1－2］。同时也可以看出其弊端，当属性基数很大时，位串就会比较长，在时间和空间上开销都会很大。针对该问题学者们提出了很多数据压缩技术，诸如WAH、BBC、分段编码，以及将WAH 和分段编码相结合的方法等［3－5］。但压缩率与0和1位串的连续分布性有直接关系，并没有使编码空间得到充分的利用。

编码位图索引是通过对简单位图索引位串中只有一个1、多个0的情况进行改进，其位数等于先对属性的基数进行对数运算，然后将其向上取整的结果［6－7］。现有的编码位图索引方式是采用对属性进行静态的编码，这样在使用数据表之前，属性所有取值情况的编码值都已经存在，并且在修改数据表时，即使没有某属性值也会为其分配编码值，在一定程度上浪费了存储空间。另外，目前已有的编码位图索引技术大都是基于B＋树建立的索引存储结构［8－9］。……