BITMAP索引的物理結構。
1.索引鍵值對應單條記錄的情況
SQL> create table test_bitmap (id number, name varchar2(20), age number(3));
表已創建。
SQL> create bitmap index ind_b_test_bitmap_age on test_bitmap (age);
索引已創建。
SQL> set serverout on
SQL> exec p_unused_space('ind_b_test_bitmap_age', 'index')
total_blocks is 64
total_bytes is 1048576
unused_blocks is 60
unused_bytes is 983040
last_used_extent_file_id is 11
last_used_extent_block_id is 1348
last_used_block is 4
PL/SQL 過程已成功完成。
SQL> insert into test_bitmap values (1, 'aaa', 1);
已創建 1 行。
SQL> alter system dump datafile 11 block 1352;
系統已更改。
Leaf block dump
===============
header address 141643364=0x8714e64
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 16201=0x3f49
kdxcoavs 16161
kdxlespl 0
kdxlende 1
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 16228
row#0[16201] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 1; (1): 00 當一個段中，只有一條記錄的時候，oracle不是採用bitmap映射的方式，而是直接給出這條記錄在這個段中的位置。例如這裡的00表示了這個段中的第一條記錄
row#1[16222] flag: ---D-, lock: 2
col 0; NULL
col 1; NULL
col 2; NULL
col 3; NULL
----- end of leaf block dump -----
End dump data blocks TSN: 11 file#: 11 minblk 1352 maxblk 1352
SQL> insert into test_bitmap values (2, 'aaa', 1);
已創建 1 行。
SQL> insert into test_bitmap values (3, 'a', 2);
已創建 1 行。
SQL> select rowid, id, age from test_bitmap;
ROWID ID AGE
------------------ ---------- ----------
AAAH2WAALAAAAUWAAA 1 1
AAAH2WAALAAAAUWAAB 2 1
AAAH2WAALAAAAUWAAC 3 2
SQL> alter system dump datafile 11 block 1352;
系統已更改。
Leaf block dump
===============
header address 141643364=0x8714e64
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 4
kdxcosdc 0
kdxconro 4
kdxcofbo 44=0x2c
kdxcofeo 16158=0x3f1e
kdxcoavs 16114
kdxlespl 0
kdxlende 2
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 16228
row#0[16201] flag: ---D-, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 1; (1): 00
row#1[16179] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 2; (2): c8 03 一旦這個索引段中存放的記錄超過兩條就採用了bit位置表示法
row#2[16158] flag: -----, lock: 2
col 0; len 2; (2): c1 03
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 1; (1): 02 這個02表示的是第三條記錄。不過這個還不好確定02表示的相對位置還是就是rowid的最後兩位。
row#3[16222] flag: ---D-, lock: 2
col 0; NULL
col 1; NULL
col 2; NULL
col 3; NULL
----- end of leaf block dump -----
End dump data blocks tsn: 11 file#: 11 minblk 1352 maxblk 1352
SQL> insert into test_bitmap select 3+rownum, 'a', 1 from user_tables where rownum < 7;
已創建6行。
SQL> insert into test_bitmap values (10, 'b', 3);
已創建 1 行。
SQL> select rowid, id, age from test_bitmap;
ROWID ID AGE
------------------ ---------- ----------
AAAH2WAALAAAAUWAAA 1 1
AAAH2WAALAAAAUWAAB 2 1
AAAH2WAALAAAAUWAAC 3 2
AAAH2WAALAAAAUWAAD 4 1
AAAH2WAALAAAAUWAAE 5 1
AAAH2WAALAAAAUWAAF 6 1
AAAH2WAALAAAAUWAAG 7 1
AAAH2WAALAAAAUWAAH 8 1
AAAH2WAALAAAAUWAAI 9 1
AAAH2WAALAAAAUWAAJ 10 3
已選擇10行。
SQL> alter system dump datafile 11 block 1352;
系統已更改。
Leaf block dump
===============
header address 141636196=0x8713264
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 4
kdxcosdc 0
kdxconro 7
kdxcofbo 50=0x32
kdxcofeo 16094=0x3ede
kdxcoavs 16044
kdxlespl 0
kdxlende 3
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 16228
row#0[16201] flag: ---D-, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 1; (1): 00
row#1[16179] flag: ---D-, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 2; (2): c8 03
row#2[16136] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 2; (2): c8 fb
row#3[16115] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 08
col 2; len 6; (6): 02 c0 05 16 00 0f
col 3; len 1; (1): 00
row#4[16158] flag: -----, lock: 2
col 0; len 2; (2): c1 03
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 1; (1): 02
row#5[16094] flag: -----, lock: 2
col 0; len 2; (2): c1 04 age = 3
col 1; len 6; (6): 02 c0 05 16 00 08
col 2; len 6; (6): 02 c0 05 16 00 0f
col 3; len 1; (1): 01 這回我們可以確定，這個值是相對位置而不是rowid的後兩位了。參考上面的rowid值，age=3的記錄是這個索引段的第二條記錄
row#6[16222] flag: ---D-, lock: 2
col 0; NULL
col 1; NULL
col 2; NULL
col 3; NULL
----- end of leaf block dump -----
End dump data blocks tsn: 11 file#: 11 minblk 1352 maxblk 1352
2.索引鍵值對應多條記錄的情況
在上面的例子中
SQL> select rowid, id, age from test_bitmap;
ROWID ID AGE
------------------ ---------- ----------
AAAH2WAALAAAAUWAAA 1 1
AAAH2WAALAAAAUWAAB 2 1
AAAH2WAALAAAAUWAAC 3 2
AAAH2WAALAAAAUWAAD 4 1
AAAH2WAALAAAAUWAAE 5 1
AAAH2WAALAAAAUWAAF 6 1
AAAH2WAALAAAAUWAAG 7 1
AAAH2WAALAAAAUWAAH 8 1
AAAH2WAALAAAAUWAAI 9 1
AAAH2WAALAAAAUWAAJ 10 3
row#2[16136] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 2; (2): c8 fb
把fb變為二進制：11111011
與上面的rowid結合可以看出，這種情況下，有1的位置表示這條記錄符合當前索引的鍵值。
從高位到低位分別表示了這個索引段中的第8表記錄到第1條記錄。
SQL> insert into test_bitmap select 11+rownum, 'a', 4 from dba_tables where rownum < 81;
已創建80行。
SQL> alter system dump datafile 11 block 1352;
系統已更改。
Leaf block dump
===============
header address 141636196=0x8713264
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 4
kdxcosdc 0
kdxconro 8
kdxcofbo 52=0x34
kdxcofeo 16061=0x3ebd
kdxcoavs 16009
kdxlespl 0
kdxlende 3
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 16228
row#0[16201] flag: ---D-, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 1; (1): 00
row#1[16179] flag: ---D-, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 2; (2): c8 03
row#2[16136] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 2; (2): c8 fb
row#3[16115] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 c0 05 16 00 08
col 2; len 6; (6): 02 c0 05 16 00 0f
col 3; len 1; (1): 00
row#4[16158] flag: -----, lock: 2
col 0; len 2; (2): c1 03
col 1; len 6; (6): 02 c0 05 16 00 00
col 2; len 6; (6): 02 c0 05 16 00 07
col 3; len 1; (1): 02
row#5[16094] flag: -----, lock: 2
col 0; len 2; (2): c1 04
col 1; len 6; (6): 02 c0 05 16 00 08
col 2; len 6; (6): 02 c0 05 16 00 0f
col 3; len 1; (1): 01
row#6[16061] flag: -----, lock: 2
col 0; len 2; (2): c1 05
col 1; len 6; (6): 02 c0 05 16 00 08
col 2; len 6; (6): 02 c0 05 16 00 5f
col 3; len 13; (13): cf fc ff ff ff ff ff ff ff ca ff ff 03
row#7[16222] flag: ---D-, lock: 2
col 0; NULL
col 1; NULL
col 2; NULL
col 3; NULL
----- end of leaf block dump -----
End dump data blocks tsn: 11 file#: 11 minblk 1352 maxblk 1352
我們繼續看這個例子：
由於範圍08－0f之間還有空閒空間，索引範圍分配還是從08開始，一個80條記錄，由於前8個位置中有其他記錄，索引一個分配了5×16＋15－8＋1＝88個rowid的範圍。
fc變為二進制是11111100，最低二位已經被占有，索引這個索引段存儲了6條記錄。
而最後一個索引段存儲了兩條記錄 03 －> 00000011，加在一起正好是80條記錄。
中間的ca和開頭的cf，不是索引的bitmap，而是類似數據頭之類的東西，具體數值代表什麼我還不清楚，不過似乎每64位就會出現一個數據頭。
根據上面的幾個例子，索引段中的bitmap編碼如實反應了記錄在索引段中的位置。
簡單的說，BITMAP索引記錄為每個不同的鍵值建立一條或多條記錄（和數據的物理分布有關）。每條記錄包括起始ROWID、終止ROWID和起始終止ROWID之間的所有記錄中，滿足索引列等於當前鍵值的行的BIT編碼。
BITMAP和B*TREE INDEX的結構是相似的，這裡主要分析下BITMAP的結構，和表達一個觀點：不是LOW CANDIDATE的列都是適合做BITMAP的。
眾所周知,BITMAP的一些特性是
1、DELETE,UPDATE,INSERT比較耗時。
2、適合low-cardinality的COLUMN。
3、得到的結果占表行數的比例較大時，也是效率較高的。
BITMAP和B*TREE有很大區別，B TREE INDEX 的每一個NODE最多有2n個值2n+1個POINT，（如果LEFT，RIGHT頁節點都存在的話）。最少有d個值和d+1個point （如果是一顆歪的樹的話，n,d指的是樹的層數）。樹的LEFT是小的值。
BITMAPINDEX的並發性很不好，甚至兩個會話作相同的INSERT都會發生DEADLOCK，如果一個SESSION批量DML則表現很好,實驗如下：
create table wwm nologging as
Select rownum id,mod(rownum,10) btree_col,mod(rownum,10) bitmap_col, rpad(‘x’,200) padding from all_objects where rownum<3000;
此時，表中有2999條記錄，並且btree_col,bitmap_col里的值都是0—9，
分別建立兩個索引
SQL> CREATE INDEX wwm_tree on wwm(btree_col);
SQL> create bitmap index wwm_bit on wwm(bitmap_col);
本庫是ORACLE 9 資料庫的塊大小是8k
analyze index wwm_tree validate STRUCTURE ;
analyze table wwm estimate statistics
1* select blocks,LF_BLKS from index_stats where
BLOCKS LF_BLKS
---------- ----------
16 6
select blocks,LF_BLKS from index_stats where
BLOCKS LF_BLKS
---------- ----------
16 1
1 select segment_name||' '||file_id||' '||tablespace_name||' '||block_id||' '||blocks from dba_extents where segment_name="WWM_TREE" or segment_name="WWM_BIT"
SEGMENT_NAME||''||FILE_ID||''||TABLESPACE_NAME||''||BLOCK_ID||''||BLOCKS
--------------------------------------------------------------------------------
WWM_TREE 14 DATA04 201 16
WWM_BIT 14 DATA04 217 16
同時，也可以做實驗，通過以上SQL看看是什麼對index的大小有影響，結果是只有COLUMN的長度和ROWS會有影響，而是否LOW cardinality不會有影響，將BITMAP INDEX的列用seqUENCE代替後大小几乎沒有差別。由於本庫的EXTENT較大，不在這裡舉例了。大家還可以看到LOW cardinality的BITMAP所占用的空間要比B*TREE小很多。
1* select object_id||' '||Object_name from dba_objects where object_name="WWM_TREE" or objecT_name="WWM_BIT"
OBJECT_ID||''||OBJECT_NAME
--------------------------------------------------------------------------------
32099 WWM_BIT
32098 WWM_TREE
DUMP BLOCK的 數據結構出來分析
alter system dump datafile 14 block 201 ;
alter system dump datafile 14 block 217 ;
DUMP OBJECT 的數據結構出來分析
SQL> alter session set events 'IMMEDIATE TRACE NAME TREEDUMP LEVEL 32098'
SQL> alter session set events 'IMMEDIATE TRACE NAME TREEDUMP LEVEL 32099’
查看Dump檔案
<<檔案頭>>
/usr/sap3/oracle/admin/SIDDB/udump/siddb_ora_23096.trc
Oracle9i Enterprise Edition Release 9.2.0.1.0 - 64bit Production
With the Partitioning, OLAP and Oracle Data Mining options
JServer Release 9.2.0.1.0 - Production
ORACLE_HOME = /usr/sap3/oracle/product/920
System name: HP-UX
…………………………………………
*** SESSION ID:(11.3039) 2006-10-31 17:22:15.378
〈〈alter system dump datafile 14 block 201 ;〉〉 的結果
Start dump data blocks tsn: 14 file#: 14 minblk 201 maxblk 201
buffer tsn: 14 rdba: 0x038000c9 (14/201)
scn: 0x0000.0007b8f6 seq: 0x02 flg: 0x00 tail: 0xb8f62002
frmt: 0x02 chkval: 0x0000 type: 0x20=FIRST LEVEL BITMAP BLOCK
Dump of First Level Bitmap Block
--------------------------------
nbits : 2 nranges: 1 parent dba: 0x038000ca poffset: 0
unformatted: 6 total: 16 first useful block: 3
owning Instance : 1
instance ownership changed at 10/31/2006 16:53:57
Last successful Search 10/31/2006 16:53:57
Freeness Status: nf1 0 nf2 1 nf3 0 nf4 0
Extent Map Block Offset: 4294967295
First free datablock : 3
Bitmap block lock opcode 0
locker xid: : 0x0000.000.00000000
Highwater:: 0x038000d3 ext#: 0 blk#: 10 ext size: 16
#blocks in seg. hdr's freelists: 0
#blocks below: 10
mapblk 0x00000000 offset: 0
HWM Flag: HWM Set
--------------------------------------------------------
DBA Ranges :
--------------------------------------------------------
0x038000c9 Length: 16 Offset: 0
0:Metadata 1:Metadata 2:Metadata 3:25-50% free
4:FULL 5:FULL 6:FULL 7:FULL
8:FULL 9:FULL 10:unformatted 11:unformatted
12:unformatted 13:unformatted 14:unformatted 15:unformatted
--------------------------------------------------------
End dump data blocks tsn: 14 file#: 14 minblk 201 maxblk 201
〈〈alter system dump datafile 14 block 217 〉〉的結果
*** 2006-10-31 17:23:20.602
Start dump data blocks tsn: 14 file#: 14 minblk 217 maxblk 217
buffer tsn: 14 rdba: 0x038000d9 (14/217)
scn: 0x0000.0007b904 seq: 0x02 flg: 0x00 tail: 0xb9042002
frmt: 0x02 chkval: 0x0000 type: 0x20=FIRST LEVEL BITMAP BLOCK
Dump of First Level Bitmap Block
--------------------------------
nbits : 2 nranges: 1 parent dba: 0x038000da poffset: 0
unformatted: 12 total: 16 first useful block: 3
owning instance : 1
instance ownership changed at 10/31/2006 16:54:13
Last successful Search 10/31/2006 16:54:13
Freeness Status: nf1 0 nf2 1 nf3 0 nf4 0
Extent Map Block Offset: 4294967295
First free datablock : 3
Bitmap block lock opcode 0
Locker xid: : 0x0000.000.00000000
Highwater:: 0x038000dd ext#: 0 blk#: 4 ext size: 16
#blocks in seg. hdr's freelists: 0
#blocks below: 1
mapblk 0x00000000 offset: 0
HWM Flag: HWM Set
--------------------------------------------------------
DBA Ranges :
--------------------------------------------------------
0x038000d9 Length: 16 Offset: 0
0:Metadata 1:Metadata 2:Metadata 3:25-50% free
4:unformatted 5:unformatted 6:unformatted 7:unformatted
8:unformatted 9:unformatted 10:unformatted 11:unformatted
12:unformatted 13:unformatted 14:unformatted 15:unformatted
--------------------------------------------------------
End dump data blocks tsn: 14 file#: 14 minblk 217 maxblk 217
*** 2006-10-31 18:19:00.639
----- begin tree dump
〈〈alter session set events 'IMMEDIATE TRACE NAME TREEDUMP LEVEL 32098'〉〉的結果
branch: 0x38000cc 58720460 (0: nrow: 6, level: 1) ---branch block指向兩個LEAF NODE
leaf: 0x38000cd 58720461 (-1: nrow: 533 rrow: 533) --leaf block，有533對LEAF節點
Leaf block dump
===============
header address 13835058057859399780=0xc0000000999d8064
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 533
kdxcofbo 1102=0x44e
kdxcofeo 1919=0x77f
kdxcoavs 817
kdxlespl 0
kdxlende 0
kdxlenxt 58720462=0x38000ce
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8016
row#0[8005] flag: -----, lock: 0
col 0; len 1; (1): 80
col 1; len 6; (6): 03 80 00 1c 00 09
row#1[7994] flag: -----, lock: 0
col 0; len 1; (1): 80
col 1; len 6; (6): 03 80 00 1c 00 13
…………………………………………….
row#532[1919] flag: -----, lock: 0
col 0; len 2; (2): c1 02
col 1; len 6; (6): 03 80 00 76 00 14
----- end of leaf block dump -----
leaf: 0x38000ce 58720462 (0: nrow: 511 rrow: 511)
Leaf block dump
===============
header address 13835058057859653732=0xc000000099a16064
……………………………………………………
row#0[8004] flag: -----, lock: 0
col 0; len 2; (2): c1 02
col 1; len 6; (6): 03 80 00 76 00 1e
row#1[7992] flag: -----, lock: 0
col 0; len 2; (2): c1 02
col 1; len 6; (6): 03 80 00 77 00 07
。。。。。。。。。。。。。。。。。。。。。。。
row#510[1884] flag: -----, lock: 0
col 0; len 2; (2): c1 04
col 1; len 6; (6): 03 80 00 5a 00 17
----- end of leaf block dump -----
leaf: 0x38000cf 58720463 (1: nrow: 511 rrow: 511)
Leaf block dump
…………………………………………………………………….
header address 13835058057859620964=0xc000000099a0e064
……………………………………………………………..
row#0[8004] flag: -----, lock: 0
col 0; len 2; (2): c1 09
col 1; len 6; (6): 03 80 00 65 00 05
row#1[7992] flag: -----, lock: 0
col 0; len 2; (2): c1 09
col 1; len 6; (6): 03 80 00 65 00 0f
………………………………………………………………….
row#8[7908] flag: -----, lock: 0
col 0; len 2; (2): c1 09
col 1; len 6; (6): 03 80 00 67 00 13
row#9[7896] flag: -----, lock: 0
