关于Oracle位图索引内部浅论

我们都知道Oracle位图索引适用于字段不同值很少的情况，同时修改DML会导致整个同样的值全部被锁定，这严重影响了并发性，所以不建议OLTP系统大量使用位图索引。
但是具体位图索引的内部是如何排列和组织的呢？如下将进行探讨，由于水平有限可能有一定错误。
首先认识BITMAP索引的组织方式，首先看一下ORACLE给出的这张图

可以看到本图中实际上有4种颜色蓝色、绿色、红色、黄色，BITMAP 索引也是B-TREE的格式，但是其页节点存储的是键值+ROWID范围+位图键的方式，这样一来可以很明显的感知到BITMAP所以在键值很少的时候其空间比较B-TREE索引是小很多的，而在位图键方面使用一连串的0和1来表示是否存在相应的值，这样一来ORACLE就能快速的进行是否有值的定位。

接下来我们进行DUMP，先建立测试表

建立这样一张表
SQL> select id,count(*) from testt_bit group by id;
          ID  COUNT(*)
 ----------- ----------
          1    100000
          2    100000
          3    100000
同时在分布上是连续的，1是1-100000行，2是100001-200000行，3是剩下的
 在ID列上建立BIT MAP索引
create bitmap index TEST_BIT_IND on TESTT_BIT (ID)

首先进行BITMAP索引的结构DUMP如下：
SQL> oradebug setmypid
 Statement processed.
 SQL> oradebug tracefile_name
 /ora11g/diag/rdbms/test/test/trace/test_ora_5604.trc
 SQL> alter session set events 'immediate trace name treedump level 76306';

*** 2015-03-18 00:40:35.111
 ----- begin tree dump
 branch: 0x1000333 16778035 (0: nrow: 8, level: 1)
    leaf: 0x1000334 16778036 (-1: nrow: 2 rrow: 2)
    leaf: 0x1000335 16778037 (0: nrow: 2 rrow: 2)
    leaf: 0x1000336 16778038 (1: nrow: 2 rrow: 2)
    leaf: 0x1000337 16778039 (2: nrow: 2 rrow: 2)
    leaf: 0x1000338 16778040 (3: nrow: 2 rrow: 2)
    leaf: 0x1000339 16778041 (4: nrow: 2 rrow: 2)
    leaf: 0x100033a 16778042 (5: nrow: 2 rrow: 2)
    leaf: 0x100033b 16778043 (6: nrow: 1 rrow: 1)
 ----- end tree dump
这里清楚的看到了这个位图索引的层次，首先它只有2层，1个根节点8个页节点，每个叶节点包含2个索引条目（最后一个节点除外）

接下来我们DUMP根节点：
 根据DBA(block adress)16778035进行换算
SQL>  select dbms_utility.data_block_address_file(16778035),
  2  dbms_utility.data_block_address_block(16778035) from dual;
 DBMS_UTILITY.DATA_BLOCK_ADDRES DBMS_UTILITY.DATA_BLOCK_ADDRES
 ------------------------------ ------------------------------
                              4                            819
然后alter system dump datafile 4 block 819进行DUMP

header address 47810796042828=0x2b7bd183ba4c
 kdxcolev 1
 KDXCOLEV Flags = - - -
 kdxcolok 0
 kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
 kdxconco 4
 kdxcosdc 0
 kdxconro 7
 kdxcofbo 42=0x2a
 kdxcofeo 7972=0x1f24
 kdxcoavs 7930
 kdxbrlmc 16778036=0x1000334
 kdxbrsno 0
 kdxbrbksz 8056
 kdxbr2urrc 0
关于这一部分引用一个文档（作者不详）
 其中的kdxcolev表示索引层级号，这里由于我们转储的是根节点，所以其层级号为1。对叶子节点来说该值为0；
 kdxcolok表示该索引上是否正在发生修改块结构的事务；kdxcoopc表示内部操作代码；kdxconco表示索引条目中列的数量；
 kdxcosdc表示索引结构发生变化的数量，当你修改表里的某个索引键值时，该值增加；kdxconro表示当前索引节点中索引条目的数量，但是注意，不包括kdxbrlmc指针；kdxcofbo表示当前索引节点中可用空间的起始点相对当前块的位移量；
 kdxcofeo表示当前索引节点中可用空间的最尾端的相对当前块的位移量；kdxcoavs表示当前索引块中的可用空间总量，也就是用kdxcofeo减去kdxcofbo得到的。kdxbrlmc表示分支节点的地址，该分支节点存放了索引键值小于row#0（在转储文档后半部分显示） 所含有的最小值的所有节点信息；kdxbrsno表示最后一个被修改的索引条目号，这里看到是0，表示该索引是新建的索引；
kdxbrbksz表示可用数据块的空间大小。实际从这里已经可以看到，即便是PCTFREE设置为0，也不能用足8192字节。

row#0[8044] dba: 16778037=0x1000335
 col 0; len 2; (2):  c1 02
 col 1; len 3; (3):  01 00 03
 col 2; TERM
 row#1[8031] dba: 16778038=0x1000336
 col 0; len 2; (2):  c1 02
 col 1; len 4; (4):  01 00 03 f8
 col 2; TERM
 row#2[8019] dba: 16778039=0x1000337
 col 0; len 2; (2):  c1 03
 col 1; len 3; (3):  01 00 04
 col 2; TERM
 row#3[8006] dba: 16778040=0x1000338
 col 0; len 2; (2):  c1 03
 col 1; len 4; (4):  01 00 04 bf
 col 2; TERM
 row#4[7998] dba: 16778041=0x1000339
 col 0; len 2; (2):  c1 04
 col 1; TERM
 row#5[7985] dba: 16778042=0x100033a
 col 0; len 2; (2):  c1 04
 col 1; len 4; (4):  01 00 05 57
 col 2; TERM
 row#6[7972] dba: 16778043=0x100033b
 col 0; len 2; (2):  c1 04
 col 1; len 4; (4):  01 00 05 f8
 col 2; TERM

这一部分是具体的关于各个叶节点的位置（起始位置的叶节点已经在kdxbrlmc 16778036=0x1000334给出）
 其存储方式为COL0 键值+COL1其对应的表中数据块起始的DBA（可能包含BMB LEVEL1块）
 但是这里
row#4[7998] dba: 16778041=0x1000339
col 0; len 2; (2):  c1 04
col 1; TERM
并未包含实际的表的DBA，为什么未知

Auxillary Map
  --------------------------------------------------------
    Extent 0    :  L1 dba:  0x01000130 Data dba:  0x01000133
    Extent 1    :  L1 dba:  0x01000130 Data dba:  0x01000138
    Extent 2    :  L1 dba:  0x01000140 Data dba:  0x01000141
    Extent 3    :  L1 dba:  0x01000140 Data dba:  0x01000148
    Extent 4    :  L1 dba:  0x01000150 Data dba:  0x01000151
    Extent 5    :  L1 dba:  0x01000150 Data dba:  0x01000158
    Extent 6    :  L1 dba:  0x01000160 Data dba:  0x01000161
    Extent 7    :  L1 dba:  0x01000160 Data dba:  0x01000168
    Extent 8    :  L1 dba:  0x01000170 Data dba:  0x01000171
    Extent 9    :  L1 dba:  0x01000170 Data dba:  0x01000178
    Extent 10    :  L1 dba:  0x01000300 Data dba:  0x01000301
    Extent 11    :  L1 dba:  0x01000300 Data dba:  0x01000308
    Extent 12    :  L1 dba:  0x01000310 Data dba:  0x01000311
    Extent 13    :  L1 dba:  0x01000310 Data dba:  0x01000318
    Extent 14    :  L1 dba:  0x01000320 Data dba:  0x01000321
    Extent 15    :  L1 dba:  0x01000320 Data dba:  0x01000328
    Extent 16    :  L1 dba:  0x01000380 Data dba:  0x01000382
    Extent 17    :  L1 dba:  0x01000400 Data dba:  0x01000402
    Extent 18    :  L1 dba:  0x01000480 Data dba:  0x01000482
    Extent 19    :  L1 dba:  0x01000500 Data dba:  0x01000502
    Extent 20    :  L1 dba:  0x01000580 Data dba:  0x01000582
比如：
row#2[8019] dba: 16778039=0x1000337
 col 0; len 2; (2):  c1 03
 col 1; len 3; (3):  01 00 04 
根据COL 1 01 00 04 实际是01000400，我们在BMB LEVEL3的dump中可以找到
  Extent 17    :  L1 dba:  0x01000400 Data dba:  0x01000402
实际上它是一个BMB LEVEL1块，我们可以看他的数据块实际上是0x01000402
可以进行DUMP这个数据块是否是C1 03这个值
SQL> oradebug setmypid
 Statement processed.
 SQL> oradebug tracefile_name
 /ora11g/diag/rdbms/test/test/trace/test_ora_6108.trc
 SQL>  alter system dump datafile 4 block 1026;
截取第一行
tab 0, row 0, @0x1f89
 tl: 15 fb: --H-FL-- lb: 0x1  cc: 2
 col  0: [ 8]  67 61 6f 70 65 6e 67 32
 col  1: [ 2]  c1 03
 tab 0, row 1, @0x1f7a
可以看到这里的col  1确实为C1 03

接下来取出其中一个块进行分析
 这里为了更方便的论述，我将数据ID的分布变为123123这样的分布而非连续的分布，这样更能清晰看到位图在分布中的变化。如果为连续,那么会全部是是FF这样的出现，根据DUMP的BITMAP的索引结构我取出其中一个块进行分析如下：

Leaf block dump
 ===============
 header address 47520285706852=0x2b382dbfca64
 kdxcolev 0
 KDXCOLEV Flags = - - -
 kdxcolok 0
 kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
 kdxconco 4
 kdxcosdc 0
 kdxconro 2
 kdxcofbo 40=0x28
 kdxcofeo 950=0x3b6
 kdxcoavs 910
 kdxlespl 0
 kdxlende 0
 kdxlenxt 20971653=0x1400085
 kdxleprv 0=0x0
 kdxledsz 0
 kdxlebksz 8032

row#0[4492] flag: ------, lock: 0, len=3540
 col 0; len 2; (2):  c1 02
 col 1; len 6; (6):  01 00 03 43 00 00
 col 2; len 6; (6):  01 00 03 7c 00 3f
 col 3; len 3519; (3519):
  cf 49 92 24 49 92 24 49 92 cf 24 49 92 24 49 92 24 49 cf 92 24 49 92 24 49
  .....
  49 92 24 49 92 24 49 92 02 ff 1e 49 92 24 49 92 24 49 92
 row#1[950] flag: ------, lock: 0, len=3542
 col 0; len 2; (2):  c1 02
 col 1; len 6; (6):  01 00 03 7c 00 40
 col 2; len 6; (6):  01 00 06 36 00 7f
 col 3; len 3521; (3521):
  cf 24 49 92 24 49 92 24 49 cf 92 24 49 92 24 49 92 24 cf 49 92 24 49 92 24
  .....
  92 02 ff 1e 49 92 24 49 92 24 49 92 cf 24 49 92 24 49 92 24 49
 
由于在位图索引中每一个键值被压缩为键值+ROWID范围+位图键的方式，这里对于row#0
可以看到
col 0; len 2; (2):  c1 02为键值
col 1; len 6; (6):  01 00 03 43 00 00
 col 2; len 6; (6):  01 00 03 7c 00 3f
为ROWID的范围
col 3; len 3519 就是他的位图键，由于位图键非常长，我们主要取出
cf 49 92 24 49 92 24 49 92
这个片段进行分析
 首先cf应该是一个标示位（作用未知）
 剩下的
49 92 24 49 92 24 49 92 我们进行分析，实际上这里每一个FF代表了一个字节，一个字节8位FF代表是的11111111
 SQL> select to_number('49','xxxxxxxxxxxxxx') from dual;
 TO_NUMBER('49','XXXXXXXXXXXXXX
 ------------------------------
                            73

SQL> select to_number('92','xxxxxxxxxxxxxx') from dual;
 TO_NUMBER('92','XXXXXXXXXXXXXX
 ------------------------------
                            146

SQL> select to_number('24','xxxxxxxxxxxxxx') from dual;
 TO_NUMBER('24','XXXXXXXXXXXXXX
 ------------------------------
                            36
实际上他们的十进制为73 146 36 73 146 36 73 146
我们转换为2进制然后进行取反同时不足不满8位的如下：
10010010(73) 01001001(146) 00100100(36) 10010010(73) 01001001(146) 00100100(36) 10010010(73) 01001001(146)
那么组合下来如下：
1001001001001001001001001001001001001001001001001001001001001001
其中每一个位图BIT代表一个ROWID他们是连续的，根据起始方位ROWID是能推算出来的。
 这样可以清晰的看到表中字段1的取值（实际上c1 02=1）位图如上，他们是交替出现和我表中数据一样如下：
SQL> select dbms_rowid.rowid_block_number(rowid),dbms_rowid.rowid_row_number(rowid),TESTt_bi2.*  from TESTT_BI2 where dbms_rowid.rowid_block_number(rowid)=835;
 DBMS_ROWID.ROWID_BLOCK_NUMBER( DBMS_ROWID.ROWID_ROW_NUMBER(RO NAME                          ID
 ------------------------------ ------------------------------ -------------------- -----------
                            835                              0 gaopeng                        1
                            835                              1 gaopeng                        2
                            835                              2 gaopeng                        3
                            835                              3 gaopeng                        1
                            835                              4 gaopeng                        2
                            835                              5 gaopeng                        3
                            835                              6 gaopeng                        1
                            835                              7 gaopeng                        2
                            835                              8 gaopeng                        3
                            835                              9 gaopeng                        1
                            835                            10 gaopeng                        2
                            835                            11 gaopeng                        3
                            835                            12 gaopeng                        1
                            835                            13 gaopeng                        2
                            835                            14 gaopeng                        3
                            835                            15 gaopeng                        1
                            835                            16 gaopeng                        2
                            835                            17 gaopeng                        3
 ..........
这段如果理解一下就是
 如果SELECT * FROM TEABLE WHERE ID=1
那么这时候位图中取值为1的都是满足条件的，将会被取出（根据ROWID)

关于阅读这部分信息参考
What is 6D DB B6?
 6D = 1101101
 DB = 11011011
 B6 = 10110110
 Read from least significant bit (right to left) and left pad with zeros if not eight bits.
 The resulting map is
 10110110 11011011 01101101
 An important point is to read the bitmap from left to right in hexadecimal in two-byte
 chunks. Read each of those chunks in binary right (least significant bit) to left. If there
 are not eight bits, then these would have been in effect, leading zeros, and are treated
 as such. The underlined zero above demonstrates this.