oracle10g对于bitmap index的改进

NinGoo · 发表于 2007-3-27 15:02

前面猜的东西还是有不少是不准确的

我们知道bitmap index本身是按照btree来组织的，每个叶块中存储具体的entry，每个entry包含索引值，起始rowid，终止rowid，和位图块四部分。

注意这里的位图块采用了压缩存储的方式，不过只压缩前缀值为0的bit，不压缩值为1的bit和中间的0，每个位图段

使用一个或者多个字节来做为控制位，也就是前面试验中我猜测的标志长度字节和后面一些有疑问的字节。

简单的描述一下位图块的压缩算法如下：

如果位图块只有一个1，其余全0，则只需要通过控制位来表示该1所在的位置

比如，00 表示 1000 0000，也就是1处在起始rowid的位置
01 表示 0100 0000，也就是1是在起始rowid下一条的位置

这样，只有一条数据的情况下，只需要用一个控制位来表示1的具体位置，而不需要后续的位图块了。最多可以表示1个1＋191个0的情况，也就是控制位小于192(0xc0)都表示只有1个值，根据控制位oracle可以知道这个1的具体位置。

如果有多个1，则第一个控制字节的前两个bit一般为11，紧跟的3个bit表示跳过的全0的字节数（注意这里是字节数），如果0的的字节数太多，3个bit全为1以后，就再多分配一个字节，如果第二个字节的最高位变成1，则再分配第三个字节。

第一个控制字节的最后三位则表示控制字节后面的位图块的长度，3个bit只能表示1~8，所以前面试验中可以看出每个位图段都是最多8个字节，后面就会出现新的控制字节了。

这样，前面试验中一些不理解的地方也迎刃而解了。

比如 C8 分解成二进制 11 001 000 表示没有前缀0被压缩

D0 -> 11 010 000 压缩1字节

D8 -> 11 011 000 压缩2字节

E0 -> 11 100 000 压缩3字节

E8 -> 11 101 000 压缩4字节

F0 -> 11 110 000 压缩5字节

F8 00 -> 11 111 000 00000000 压缩6字节

F8 01 -> 11 111 000 00000001 压缩7字节

F8 7F -> 11 111 000 01111111 压缩133字节

F8 80 01 -> 11 111 000 10000000 00000001 压缩134字节

F8 81 01 -> 11 111 000 10000001 00000001 压缩135字节
...

C9 -> 11 001 001 表示压缩0字节，后面的位图段为1字节

CA -> 11 001 010 表示压缩0字节，后面的位图段为2字节

按照上面的算法，基本上位图压缩的算法清楚了