bitmap索引的深入研究

1、位圖（bitmap）索引是另外一種索引類型，它的組織形式與B樹索引相同，也是一棵平衡樹。與B樹索引的區(qū)別在于葉子節(jié)點(diǎn)里存放索引條目的方式不同。從前面我們知道，B樹索引的葉子節(jié)點(diǎn)里，對于表里的每個數(shù)據(jù)行，如果被索引列的值不為空的，則會為該記錄行在葉子節(jié)點(diǎn)里維護(hù)一個對應(yīng)的索引條目。而位圖索引則不是這樣，其葉子節(jié)點(diǎn)里存放的索引條目如下圖所示。      假設(shè)某個表T里所有的記錄在列C1上只具有三個值：01、02和03。在表T的C1列上創(chuàng)建位圖索引以后，則葉子節(jié)點(diǎn)的內(nèi)容如圖9-14所示?？梢钥吹?，位圖索引只有三個索引條目，也就是每個C1列的值

2、對應(yīng)一個索引條目。位圖索引條目上還包含表里第一條記錄所對應(yīng)的ROWID以及最后一條記錄所對應(yīng)的ROWID。索引條目的最后一部分則是由多個bit位所組成的bitmap，每個bit位就對應(yīng)一條記錄。位圖索引的結(jié)構(gòu)      當(dāng)發(fā)出where c1=01這樣的SQL語句時，oracle會去搜索01所在的索引條目，然后掃描該索引條目中的bitmap里所有的bit位。第一個bit位為1，則說明第一條記錄上的C1值為01，于是返回第一條記錄所在的ROWID（根據(jù)該索引條目里記錄的start ROWID加上行號得到該記錄所在的ROWID）。第二個b

3、it位為0，則說明第二條記錄上的C1值不為01，依此類推。另外，如果索引列為空，也會在位圖索引里記錄，也就是將對應(yīng)的bit位設(shè)置為0即可。如果索引列上不同值的個數(shù)比較少的時候，比如對于性別列（男或女）等，則使用位圖索引會比較好，因?yàn)樗鼘臻g的占用非常少（因?yàn)槎际怯胋it位來表示表里的數(shù)據(jù)行），從而在掃描索引的時候，掃描的索引塊的個數(shù)也比較少?？梢栽囅胍幌?，如果在列的不同值非常多的列上，比如主鍵列上，創(chuàng)建位圖索引，則產(chǎn)生的索引條目就等于表里記錄的條數(shù)，同時每個索引條目里的bitmap里，只有一個1，其它都是0。這樣還不如B樹索引的效率高。如果被索引的列經(jīng)常被更新的話，則不適合使用位圖索引。因?yàn)楫?dāng)

4、更新位圖所在的列時，由于要在不同的索引條目之間修改bit位，比如將第一條記錄從01變?yōu)?2，則必須將01所在的索引條目的第一個bit位改為0，再將02所在的索引條目的第一個bit位改為1。因此，在更新索引條目的過程中，會鎖定位圖索引里多個索引條目。也就是同時只能有一個用戶能夠更新表T，從而降低了并發(fā)性。      位圖索引比較適合用在數(shù)據(jù)倉庫系統(tǒng)里，不適合用在OLTP系統(tǒng)里。SQL> create table t_bitmap_test as  2  select rownum as id,trunc(dbm

5、s_random.value(1,4) as bitcol  3  from dba_objects where rownum<=20;SQL> select * from t_bitmap_test;        ID     BITCOL- -         1         

6、 3         2          2         3          1         4      

7、    3         5          3         6          1         7   

8、       1         8          2         9          3        10 

9、;         2        11          3        12          1        13&#

10、160;         1        14          3        15          2        1

11、6          2        17          3        18          2       

12、; 19          1        20          3SQL> connect hr/hr已連接。SQL> alter session set events '10608 trace name context forever, level 10'會話已更改。SQL> create bitmap i

13、ndex idx_t_bitmap_test on t_bitmap_test(bitcol);索引已創(chuàng)建。SQL> alter session set events '10608 trace name context off'會話已更改。SQL> select object_id from user_objects where object_name='IDX_T_BITMAP_TEST' OBJECT_ID-     24499SQL> alter session set events &#

14、39;immediate trace name TREEDUMP level 24499'會話已更改。10608事件用來跟蹤創(chuàng)建bitmap索引的過程。而TREEDUMP則用來轉(zhuǎn)儲索引的樹狀結(jié)構(gòu)。打開轉(zhuǎn)儲出來的文件：* SESSION ID:(7.13) 2008-06-10 14:33:46.000qerbiARwo: bitmap size is 8168qerbiIPI default pctfree=10qerbiIPI length=0qerbiAllocate pfree=127 space=8168qerbiStart first startqerbiRop: rid=0

15、0c01ce4.0000, new=Y , key: (2):  c1 04qerbiCmpSz notfound pctfree=10qerbiCmpSz adjblksize=7351 length=0qerbiRop keysize=4 maxbm=3531kdibcoinit(3116714): srid=00c01ce4.0000qerbiRop: rid=00c01ce4.0001, new=Y , key: (2):  c1 03kdibcoinit(3116698): srid=00c01ce4.0001qerbiRop: rid=00c01ce4.0002

16、, new=Y , key: (2):  c1 02kdibcoinit(311661c): srid=00c01ce4.0002qerbiRop: rid=00c01ce4.0003, new=N, key: (2):  c1 04qerbiRop: rid=00c01ce4.0004, new=N, key: (2):  c1 04qerbiRop: rid=00c01ce4.0005, new=N, key: (2):  c1 02qerbiRop: rid=00c01ce4.0006, new=N, key: (2):  c1 02qe

17、rbiRop: rid=00c01ce4.0007, new=N, key: (2):  c1 03qerbiRop: rid=00c01ce4.0008, new=N, key: (2):  c1 04qerbiRop: rid=00c01ce4.0009, new=N, key: (2):  c1 03qerbiRop: rid=00c01ce4.000a, new=N, key: (2):  c1 04qerbiRop: rid=00c01ce4.000b, new=N, key: (2):  c1 02qerbiRop: rid=00c

18、01ce4.000c, new=N, key: (2):  c1 02qerbiRop: rid=00c01ce4.000d, new=N, key: (2):  c1 04qerbiRop: rid=00c01ce4.000e, new=N, key: (2):  c1 03qerbiRop: rid=00c01ce4.000f, new=N, key: (2):  c1 03qerbiRop: rid=00c01ce4.0010, new=N, key: (2):  c1 04qerbiRop: rid=00c01ce4.0011, new

19、=N, key: (2):  c1 03qerbiRop: rid=00c01ce4.0012, new=N, key: (2):  c1 02qerbiRop: rid=00c01ce4.0013, new=N, key: (2):  c1 04kdibcoend(3116714): erid=00c01ce4.0017status=3qerbiCon: key: (2):  c1 04 srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 19 25 09kdibcoend(31166

20、98): erid=00c01ce4.0017status=3qerbiCon: key: (2):  c1 03 srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 82 c2 02kdibcoend(311661c): erid=00c01ce4.0017status=3qerbiCon: key: (2):  c1 02 srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 64 18 04這一段是創(chuàng)建bitmap索引的過程。我們先把被

21、索引的列的值換算成十六進(jìn)制：SQL> select dump(3),dump(2),dump(1) from dual;DUMP(3)            DUMP(2)            DUMP(1)- - -Typ=2 Len=2: 193,4 Typ=2 Len=2: 193,3 Typ=2 Len=2: 193,24、3、2對應(yīng)的十六進(jìn)制則是04、03、0

22、2。也就是上面轉(zhuǎn)儲部分顯示的key部分的鍵值?？梢钥吹剑琽racle在創(chuàng)建bitmap索引時，先從第一條記錄開始掃描，取出第一條記錄的鍵值（bitcol=3），也就是“qerbiRop: rid=00c01ce4.0000, new=Y , key: (2):  c1 04”。new=Y說明這是一個新的鍵值，因此會對應(yīng)到一個索引條目。掃描第二條記錄時，發(fā)現(xiàn)bitcol=2，該鍵值也是一個新的鍵值，因此產(chǎn)生一個新的索引條目，對應(yīng)“qerbiRop: rid=00c01ce4.0001, new=Y , key: (2):  c1 03”。掃描到第三條記錄時，發(fā)現(xiàn)bitcol=

23、1，該鍵值也是一個新的鍵值，因此產(chǎn)生第三個索引條目，對應(yīng)“qerbiRop: rid=00c01ce4.0002, new=Y , key: (2):  c1 02”。接下來掃描到的記錄所對應(yīng)的bitcol的值都是1、2、3中的一個，因此都不會產(chǎn)生新的索引條目，因此它們的new都為N。然后掃描完表里的所有記錄以后，開始創(chuàng)建bitmap索引條目，也就是下面的部分：qerbiCon: key: (2):  c1 04 srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 19 25 09kdibcoend(311

24、6698): erid=00c01ce4.0017status=3qerbiCon: key: (2):  c1 03 srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):  ca 82 c2 02kdibcoend(311661c): erid=00c01ce4.0017status=3qerbiCon: key: (2):  c1 02 srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4):      FILE#-&#

25、160;         2  dbms_rowid.rowid_block_number(rowid) as block#  3  from t_bitmap_test;     FILE#     BLOCK#- -       3    7396可以看到，完全符合。每個索引條目的“bitmap : (4)”部分表

26、示的也就是前面說到的bit位了，由1、0組成。按照前面bitmap的理論，這20條記錄所對應(yīng)的三個索引條目的bitmap的樣子應(yīng)該為：Key_value    start_rowid    end_rowid      理論上的bitmap         轉(zhuǎn)儲文件的bitmap1          00c01ce4.0

27、0;   00c01ce4.0017    ca 64 18 042          00c01ce4.0    00c01ce4.0017    ca 82 c2 023          00c01ce4.0    00c01ce4.0017  

28、0;  2   3          C2         C3- - -11001      100101     1001其中不足8位的前面用0補(bǔ)齊，因此，C1=00011001，C2=00100101，C3=00001001在二進(jìn)制里，每個應(yīng)該倒過來，從右到左排列，因此為：C3  &

29、#160;      C2        C100001001   00100101    2  dbms_rowid.rowid_block_number(rowid) as block#  3  from t_bitmap_2;     FILE#     BLOCK#- -   &#

30、160;     3       7428         3       7429         3       7430        

31、; 3       7431         3       7432         3       7433可以知道，這15條記錄分布在6個數(shù)據(jù)塊里。然后跟蹤對于bitcol列上的bitmap索引的創(chuàng)建過程：alter session set events

32、 '10608 trace name context forever, level 10'create bitmap index idx_t_bitmap_2 on t_bitmap_2(bitcol);alter session set events '10608 trace name context off'從轉(zhuǎn)儲出來的文件可以看到，最終形成了兩個索引條目：qerbiCon: key: (2000): 41 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

33、 srid=00c01d04.0 erid=00c01d08.7 bitmap: (11):  c8 06 c0 44 f8 b3 01 07 f8 56 06qerbiCon: key: (2000): 42 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20srid=00c01d04.0 erid=00c01d09.7 bitmap: (12):  00 f8 56 06 f8 56 07 c0 a1 01 c0 44* 2008-06-10 11:21:08.000很明顯，這里的兩個索引條目的start rowed和end rowed是不相同的。鍵值為A的索引條目為：srid=00c01d04.0 erid=00c01d08.7 bitmap: (11):   2   3  from dual;S_BLK#     E_BLK#- -7428    7432而鍵值B的索引條目為：srid=00c01d04.0 erid=00c01d09.7 bitm