點陣圖索引
資料庫索引技術之一
點陣圖索引指的是點陣圖索引(bitmap index)技術，是一類特殊的資料庫索引技術，其索引使用bit數組（或稱bitmap、bit set、bit string、bit vector）進行存儲與計算操作。
一。什麼是 點陣圖索引
點陣圖索引是一種使用點陣圖的特殊資料庫索引。
主要針對大量相同值的列而創建(例如：類別，操作員，部門ID,庫房ID等),
索引塊的一個索引行中存儲鍵值和起止Rowid,以及這些鍵值的位置編碼,
位置編碼中的每一位表示鍵值對應的數據行的有無。一個 塊可能指向的是幾十甚至成百上千行數據的位置.
這種方式存儲數據，相對於B*Tree索引，佔用的空間非常小，創建和使用非常快.
當根據鍵值查詢時，可以根據起始Rowid和點陣圖狀態，快速定位數據.
當根據鍵值做and,or或 in(x,y,..)查詢時，直接用索引地點陣圖進行或運算，快速得出結果行數據.
當select count(XX) 時，可以直接訪問索引就快速得出統計數據.
創建語法很簡單，就是在普通索引創建的語法中index前加關鍵字bitmap即可，例如:
create bitmap index H病人掛號記錄_ix_執行人 on H病人掛號記錄(執行人);
特點
1.Bitmap索引的存儲空間
相對於B*Tree索引, 點陣圖索引由於只存儲鍵值得起止Rowid和點陣圖，佔用的空間非常少.
bitmap的空間佔用主要跟以下4個因素相關:
a.表的總記錄數
b.索引列的鍵值多少，列的不同值越少，所需的點陣圖就越少.
c.操作的類型，批量插入比單條插入所需的點陣圖要少得多,8i,9i下是這樣的,10G則沒有這種區別，詳見後面的分析.
d.索引列相同鍵值的物理分佈,8i,9i中，不同塊上的數據，相同的鍵值，會建立不同的點陣圖行(段)來表示
註：本文提到的8i,9i,10g,我試驗的環境是8.1.7,9.2.0.5,10.2
2.Bitmap索引創建的速度
點陣圖索引創建時不需要排序，並且按位存儲，所需的空間也少.
B*Tree索引則在創建時需要排序，定位等操作，速度要慢得多.
3.Bitmap索引允許鍵值為空
而對 點陣圖索引列進行is null查詢時，則可以使用索引.
4.Bitmap索引對錶記錄的高效訪問
當使用count(XX),可以直接訪問索引就快速得出統計數據.
當根據 點陣圖索引的列進行and,or或 in(x,y,..)查詢時，直接用索引地點陣圖進行或運算，在訪問數據之前可事先過濾數據.
5.Bitmap索引對批量DML操作只需進行一次索引
由於通過點陣圖反映數據情況，批量操作時對索引的更新速度比B*Tree索引一行一行的處理快得多.
6.Bitmap索引的鎖機制
對於B*Tree索引,insert操作不會鎖定其它會話的DML操作.
而 點陣圖索引,由於用點陣圖反映數據，不同會話更新相同鍵值的同一點陣圖段,insert、update、delete相互操作都會發鎖定。
對於oracle 8i,9i,單行插入時，由於一個點陣圖行(點陣圖段)只記錄8行記錄，所以最多鎖住相同鍵值的8行數據的DML操作.
而批量插入時，和10G一樣，同一鍵值只有一個點陣圖行（點陣圖段），所以，相同鍵值的所有數據的DML操作都會被鎖住。
下面，針對8i,9i觀察一下鎖機制：
SQL> Declare
Begin
For i In 1..9
Loop
Insert Into H病人掛號記錄(Id,No,號別，執行人) Values(i,'G000001',1,'張1');
End Loop;
End;
/
SQL> delete H病人掛號記錄 where id=1;
不提交，另開一個會話，
SQL> delete H病人掛號記錄 where id=9;
操作可以進行，沒有鎖定。
SQL> delete H病人掛號記錄 where id=8;
操作等待，由於和另外一個會話操作的記錄的 點陣圖索引在同一個點陣圖段上（一個點陣圖段最多8行）,所以被鎖住了。
1. 點陣圖索引是Oracle資料庫在7.3版本中加入的,8i,9i企業版和個人版支持，標準版不支持.
2.基於規則的優化器無法使用Bitmap索引
3.適應於有大量重複值的列查詢
4.對於8i,9i版本，不適用於單行插入，適用於批量插入的數據,
因為單行插入時，相同鍵值，每插入8行就會生成一行索引塊中的點陣圖段，即使相同的值.
而批量插入時，相同鍵值只生成一個點陣圖段.
5.由於併發DML操作鎖定的是整個點陣圖段的大量數據行，所以 點陣圖索引主要是用於OLAP應用，也可以用於OLTP中主要為讀操作的表.
關於bitmap的兩個參數
SQL> show parameter bitmap;
NAME TYPE VALUE
bitmap_merge_area_size integer 1048576
create_bitmap_area_size integer 8388608
其中bitmap_merge_area_size是bitmap索引進行合併操作時使用的內存區域,create_bitmap_area_size是創建時使用的內存區域.
8i,9i中，需要根據bitmap的大小以及常見的使用情況來調整.
9i以上，只需設置pga_aggregate_target的值,Oracle即會自動進和內存的調整.
點陣圖索引對數據表的列的每一個鍵值分別存儲為一個點陣圖,Oracle對於不同的版本，不同的操作方式，數據生成均有差別.
對於8i,9i,
下面分3種方式來討論數據的插入:
a.一次插入一行，插入多行后，一次提交;
b.每插入一行，提交一次;
c.批量插入方式，一次提交;
對於第一種方式，觀察 點陣圖索引的變化情況.
a.假設插入8行相同鍵值的數據，如果以每行方式插入，然後一次提交，則會生成8個點陣圖
SQL> Insert Into H病人掛號記錄(Id,No,號別，執行人) Values(1,'G000001',1,'張1');
1 row inserted
SQL> /
1 row inserted
SQL> /
1 row inserted
SQL> /
1 row inserted
SQL> /
1 row inserted
SQL> /
1 row inserted
SQL> /
1 row inserted
SQL> /
1 row inserted
SQL> commit;
Commit complete
SQL> alter system dump datafile 1 block 40028;
System altered
row#0[7847] flag: -----, lock: 0
col 0; len 3; (3): d5 c5 31 --鍵值'張1'
col 1; len 6; (6): 00 40 9c 54 00 00 --rowid的起始位置
col 2; len 6; (6): 00 40 9c 54 00 07 --rowid的終止位置
col 3; len 2; (2): c8 ff --點陣圖編碼
row#1[7802] flag: -----, lock: 0
col 0; len 3; (3): d5 c5 31
col 1; len 6; (6): 00 40 9c 54 00 08
col 2; len 6; (6): 00 40 9c 54 00 0f
col 3; len 2; (2): c8 03
row#2[7780] flag: -----, lock: 0
col 0; len 3; (3): d5 c5 32
col 1; len 6; (6): 00 40 9c 54 00 08
col 2; len 6; (6): 00 40 9c 54 00 0f
col 3; len 1; (1): 02
row#3[7758] flag: -----, lock: 0
col 0; len 3; (3): d5 c5 33
col 1; len 6; (6): 00 40 9c 54 00 08
col 2; len 6; (6): 00 40 9c 54 00 0f
col 3; len 1; (1): 03
row#4[7736] flag: -----, lock: 2
col 0; len 3; (3): d5 c5 34
col 1; len 6; (6): 00 40 9c 54 00 08
col 2; len 6; (6): 00 40 9c 54 00 0f
col 3; len 1; (1): 04
row#5[7714] flag: -----, lock: 2
col 0; len 3; (3): d5 c5 35
col 1; len 6; (6): 00 40 9c 54 00 08
col 2; len 6; (6): 00 40 9c 54 00 0f
col 3; len 1; (1): 05
----- end of leaf block dump -----
但是，下次再插入一行相同鍵值得數據時，會自動合併這8行點陣圖為一行點陣圖，並生成一個新的索引點陣圖行存放剛插入行的索引:
SQL> Insert Into H病人掛號記錄(Id,No,號別，執行人) Values(1,'G000001',1,'張1');
1 row inserted
SQL> commit;
Commit complete
SQL> alter system dump datafile 1 block 40028;
System altered
row#0[7847] flag: -----, lock: 2
col 0; len 3; (3): d5 c5 31
col 1; len 6; (6): 00 40 9c 54 00 00
col 2; len 6; (6): 00 40 9c 54 00 07
col 3; len 2; (2): c8 ff
row#1[7825] flag: -----, lock: 2
col 0; len 3; (3): d5 c5 31
col 1; len 6; (6): 00 40 9c 54 00 08
col 2; len 6; (6): 00 40 9c 54 00 0f
col 3; len 1; (1): 00
----- end of leaf block dump -----
b.數據每行提交方式，與上面的情況相似，但有一點不一樣，每提交一行，拷貝原來的點陣圖，生成新的點陣圖，並標記原來的點陣圖為已刪除,
標記為已刪除的點陣圖，只有索引塊需要分配新的點陣圖時，才會清除標記為已刪除的點陣圖，重用這些空間.
在8i,9i上實驗的結果，與ITPUB的一書378頁一致.
如果1000條相同鍵值的數據插入，將生成125個包括8條記錄的點陣圖行.
c.第三種方式，批量插入數據,insert into H病人掛號記錄(Id,No,號別，執行人) select ***方式,
同一鍵值，只生成一次點陣圖，只有一個點陣圖.
SQL> Insert Into H病人掛號記錄(Id,No,號別，執行人)
Select 1,'G000001',1,'張1' From dual
Union All
Select 2,'G000002',1,'張1' From dual
Union All
Select 3,'G000003',1,'張1' From dual
Union All
Select 4,'G000004',1,'張1' From dual
Union All
Select 5,'G000005',1,'張1' From dual
Union All
Select 6,'G000006',1,'張1' From dual
Union All
Select 7,'G000006',1,'張1' From dual
Union All
Select 8,'G000006',1,'張1' From dual
Union All
Select 9,'G000006',1,'張1' From dual;
SQL> commit;
Commit complete
SQL> alter system dump datafile 1 block 40028;
System altered
row#0[8006] flag: -----, lock: 2
col 0; len 3; (3): d5 c5 31
col 1; len 6; (6): 00 40 9c 54 00 00
col 2; len 6; (6): 00 40 9c 54 00 0f
col 3; len 3; (3): c9 ff 01
row#1[8030] flag: ---D-, lock: 2
col 0; NULL
col 1; NULL
col 2; NULL
col 3; NULL
----- end of leaf block dump -----
所以, 點陣圖索引最好採用批量插入方式，這樣，每個鍵值只生成一個點陣圖。而單行數據插入方式，每個鍵值將每8行數據生成一個點陣圖.
10G的情況，則簡單得多.
上面3種方式，相同鍵值得插入，點陣圖的生成是一樣的，只有一個點陣圖，並且，每次提交時，並不會刪除以前的點陣圖，而是直接修改對應鍵值的點陣圖.
每次插入一行數據，插入9行后提交
row#0[7763] flag: ------, lock: 2, len=29
col 0; len 3; (3): d5 c5 31
col 1; len 6; (6): 00 00 00 00 00 00
col 2; len 6; (6): 00 40 ef f2 00 0f
col 3; len 8; (8): f9 e4 d5 dc bc 01 ff 01
----- end of leaf block dump -----
再批量插入9行數據並提交
row#0[7733] flag: ------, lock: 2, len=30
col 0; len 3; (3): d5 c5 31
col 1; len 6; (6): 00 00 00 00 00 00
col 2; len 6; (6): 00 40 ef f2 00 17
col 3; len 9; (9): fa e4 d5 dc bc 01 ff ff 03
----- end of leaf block dump -----
可以看出,10G對 點陣圖索引的存儲進行了優化，一個鍵值在索引塊中只有一個點陣圖
值，其中有些結論並不是完全正確的，可以自己實驗證明，另外，該文涉及的實驗沒有標明Oracle版本，不同的版本，結果有差異.
基本信息
- 中文名
- 點陣圖索引
- 外文名
- bitmap index
- 特點
- Bitmap索引的存儲空間
- 類別
- 技術