详细介绍位图索引的压缩编码规则

《详细介绍位图索引的压缩编码规则》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、详细介绍位图索引的压缩编码规则目标：会写位图索引和压缩位图索引1.1.1、位图索引概念和可行性不说，越说越糊涂，我们直接看位图索引的例子：•设某首饰店客户信息表示为关系R(年龄,薪水)。如下是编号从1到12的记录：1:(25,60)2:(45,60)3:(50,75)4:(50,100)5:(50,120)6:(70,110)7:(85,140)8:(30,260)9:(25,400)10:(45,350)11:(50,275)12:(60,260)•属性“年龄”有7个不同值。它的位图索引有7个向量：位图索引示例（注意：有多少条记录，位图索引的二

2、进制位数的长度就有多长！）25:10000000100030:00000001000045:01000000010050:00111000001060:00000000000170:00000100000085:000000100000•属性“薪水”有10个不同值。它的位图索引有10个向量：60:11000000000075:001000000000100:000100000000110:000001000000120:000010000000140:000000100000260:000000010001275:000000000010350:

3、000000000100400:000000001000看看位图索引的优点吧：找出年龄范围在45～55且薪水范围在100～200的所有首饰购买者？011110000110AND000111100000=000110000000一个AND操作就找到了，很爽吧！不过大家也看到了，这些超长索引存储起来很头痛吧！没关系，看下一节4.1.2，我们怎样压缩压缩再压缩，呵呵！1.1.2、压缩位图索引大家看到了，这些位图索引的“0”好多，占用好多空间，我们的目标就是压缩这些“0”利用分段长度编码来压缩位图向量中的“0”（下面是定义，看完糊涂就继续看）•设i是位向

4、量中某个“1”之前“0”的个数•首先确定i的二进制表示位数j，j≈log2i•i可以表示为j−1个“1”和一个“0”并在其后加上i的二进制数。如果i=0或1，则j=1。编码由一个“0”开始且“0”后加上表示i的一位二进制数：即i＝1的编码为01，而i＝0的编码为00。上面看着有点乱，其实很简单，解释一下（当然我解释的更乱，大家快刀斩乱麻吧）：其实我们就是想将所有“1”前面的一串“0”用少量的二进制数字记录下来。我们找到所有的“1”（因为“1”很少），查这个1前面的0的个数，然后存储起来，存储方法如下：先写出这个代表“0个数”的数字需要占几位，占几

5、位就写几减一个“1”,然后用一个“0”做分隔符，后面再写出这个代表“0个数”的数字。下面，我用从后向前写的方式来讲解！（这样好理解）举例：（简单起见，先考虑只有一个“1”的情况，复杂情况一会再讲）假如有一个位图索引为00000000000001（不用数了，前面共13个“0”）那么咱要告诉人家有13个“0”，我们就先写上1101（二进制的13），然后在前面写上一个分隔符“0”，则变成了01101，我们再看一下，“1101”这个数需要至少4个二进制位(log213≈4)才能表示出来，那么我们就在前面写3个“1”（4－1＝3，这是此编码的规定，其实我看

6、他们就是能省则省，哈哈，不过规定了就要遵守，否则不通用），（注意：这3个“1”并不是一个二进制数字，而是简单的“1”的个数，你就当成火柴棍（小学生数数法）即可！）最后就变成了11101101。再解释：这个压缩的编码由三部分组成11101101，前面的3个“1”是说明后面的数字1101占4位，中间的“0”就是一个分隔符号，后面的1101才是我们真正要用到的数字，它是说明我们的这个位图索引是一个“1”前面的“0”的个数！！当然本例是一个“1”的情况，多个“1”的情况，就把多个“0的个数”和一个“1”的组合按先后顺序串在一起就构成了一个位图索引！！此外

7、：还有特殊情况是一个“1”前有0个“0”和1个“0”的情况，分别用00和01表示。做练习吧：位图索引：1100000010000000001请写出压缩码首先注意到这个索引中共有4个“1”，那么我们就写出这4个“子压缩码”，然后串一块。第一个“1”前面没有“0”，那就是有0个“0”呗，这就简单了：压缩码就是00(特殊情况)第二个“1”前面也是有0个“0”，那么压缩码还是00第三个“1”前面有6个“0”，那么我们开始写吧：先写二进制的6是110，前面写个分隔符“0”，变成了0110，然后我们知道6（二进制的110）至少需要3位二进制来表示，3减去1等

8、于2，最后我们在前面写2个“1”，得出110110第四个“1”前面有9个“0”，同上，先写上1001，在前面加上分隔符“0”，成为010