位圖（bitmap）索引是另外一種索引類型，它的組織形式與B樹索引相同，也是一棵平衡樹。與B樹索引的區(qū)別在于葉子節(jié)點里存放索引條目的方式不同。從前面我們知道，B樹索引的葉子節(jié)點里，對于表里的每個數(shù)據(jù)行，如果被索引列的值不為空的，則會為該記錄行在葉子節(jié)點里維護一個對應(yīng)的索引條目。
而位圖索引則不是這樣，其葉子節(jié)點里存放的索引條目如下圖所示。
假設(shè)某個表T里所有的記錄在列C1上只具有三個值：01、02和03。在表T的C1列上創(chuàng)建位圖索引以后，則葉子節(jié)點的內(nèi)容如圖9-14所示。可以看到，位圖索引只有三個索引條目，也就是每個C1列的值對應(yīng)一個索引條目。位圖索引條目上還包含表里第一條記錄所對應(yīng)的ROWID以及最后一條記錄所對應(yīng)的ROWID。索引條目的最后一部分則是由多個bit位所組成的bitmap，每個bit位就對應(yīng)一條記錄。
位圖索引的結(jié)構(gòu)
當發(fā)出where c1=’01’這樣的SQL語句時，oracle會去搜索01所在的索引條目，然后掃描該索引條目中的bitmap里所有的bit位。第一個bit位為1，則說明第一條記錄上的C1值為01，于是返回第一條記錄所在的ROWID（根據(jù)該索引條目里記錄的start ROWID加上行號得到該記錄所在的ROWID）。第二個bit位為0，則說明第二條記錄上的C1值不為01，依此類推。另外，如果索引列為空，也會在位圖索引里記錄，也就是將對應(yīng)的bit位設(shè)置為0即可。
如果索引列上不同值的個數(shù)比較少的時候，比如對于性別列（男或女）等，則使用位圖索引會比較好，因為它對空間的占用非常少（因為都是用bit位來表示表里的數(shù)據(jù)行），從而在掃描索引的時候，掃描的索引塊的個數(shù)也比較少。可以試想一下，如果在列的不同值非常多的列上，比如主鍵列上，創(chuàng)建位圖索引，則產(chǎn)生的索引條目就等于表里記錄的條數(shù)，同時每個索引條目里的bitmap里，只有一個1，其它都是0。這樣還不如B樹索引的效率高。
如果被索引的列經(jīng)常被更新的話，則不適合使用位圖索引。因為當更新位圖所在的列時，由于要在不同的索引條目之間修改bit位，比如將第一條記錄從01變?yōu)?/span>02，則必須將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(dbms_random.value(1,4)) as bitcol
3 from dba_objects where rownum<=20;
SQL> select * from t_bitmap_test;
ID BITCOL
---------- ----------
1 3
2 2
3 1
4 3
5 3
6 1
7 1
8 2
9 3
10 2
11 3
12 1
13 1
14 3
15 2
16 2
17 3
18 2
19 1
20 3
SQL> connect hr/hr
已連接。
SQL> alter session set events '10608 trace name context forever, level 10';
會話已更改。
SQL> create bitmap index 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
----------
24499
SQL> alter session set events '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.000
qerbiARwo: bitmap size is 8168
qerbiIPI default pctfree=10
qerbiIPI length=0
qerbiAllocate pfree=127 space=8168
qerbiStart first start
qerbiRop: rid=00c01ce4.0000, new=Y , key: (2): c1 04
qerbiCmpSz notfound pctfree=10
qerbiCmpSz adjblksize=7351 length=0
qerbiRop keysize=4 maxbm=3531
kdibcoinit(3116714): srid=00c01ce4.0000
qerbiRop: rid=00c01ce4.0001, new=Y , key: (2): c1 03
kdibcoinit(3116698): srid=00c01ce4.0001
qerbiRop: rid=00c01ce4.0002, new=Y , key: (2): c1 02
kdibcoinit(311661c): srid=00c01ce4.0002
qerbiRop: rid=00c01ce4.0003, new=N, key: (2): c1 04
qerbiRop: rid=00c01ce4.0004, new=N, key: (2): c1 04
qerbiRop: rid=00c01ce4.0005, new=N, key: (2): c1 02
qerbiRop: rid=00c01ce4.0006, new=N, key: (2): c1 02
qerbiRop: rid=00c01ce4.0007, new=N, key: (2): c1 03
qerbiRop: rid=00c01ce4.0008, new=N, key: (2): c1 04
qerbiRop: rid=00c01ce4.0009, new=N, key: (2): c1 03
qerbiRop: rid=00c01ce4.000a, new=N, key: (2): c1 04
qerbiRop: rid=00c01ce4.000b, new=N, key: (2): c1 02
qerbiRop: rid=00c01ce4.000c, new=N, key: (2): c1 02
qerbiRop: rid=00c01ce4.000d, new=N, key: (2): c1 04
qerbiRop: rid=00c01ce4.000e, new=N, key: (2): c1 03
qerbiRop: rid=00c01ce4.000f, new=N, key: (2): c1 03
qerbiRop: rid=00c01ce4.0010, new=N, key: (2): c1 04
qerbiRop: rid=00c01ce4.0011, new=N, key: (2): c1 03
qerbiRop: rid=00c01ce4.0012, new=N, key: (2): c1 02
qerbiRop: rid=00c01ce4.0013, new=N, key: (2): c1 04
kdibcoend(3116714): erid=00c01ce4.0017status=3
qerbiCon: key: (2): c1 04
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4): ca 19 25 09
kdibcoend(3116698): erid=00c01ce4.0017status=3
qerbiCon: key: (2): c1 03
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4): ca 82 c2 02
kdibcoend(311661c): erid=00c01ce4.0017status=3
qerbiCon: key: (2): c1 02
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4): ca 64 18 04
這一段是創(chuàng)建bitmap索引的過程。我們先把被索引的列的值換算成十六進制：
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,2
4、3、2對應(yīng)的十六進制則是04、03、02。也就是上面轉(zhuǎn)儲部分顯示的key部分的鍵值。
可以看到，oracle在創(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=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 09
kdibcoend(3116698): erid=00c01ce4.0017status=3
qerbiCon: key: (2): c1 03
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4): ca 82 c2 02
kdibcoend(311661c): erid=00c01ce4.0017status=3
qerbiCon: key: (2): c1 02
srid=00c01ce4.0 erid=00c01ce4.17 bitmap: (4): ca 64 18 04
這里的srid表示start rowid，erid表示end rowid。
可以看到總共產(chǎn)生了3個索引條目，其key分別為：04、03、02。
這3個索引條目的start rowid和end rowid的格式分兩部分，中間用點隔開，點左邊的表示文件號（從左邊第一個字節(jié)開始的4個字節(jié)表示）和數(shù)據(jù)塊號（從左邊第五個字節(jié)開始的4個字節(jié)表示），點右邊表示數(shù)據(jù)塊里的行號。這里的顯示可以看到，這20條記錄都位于相同的數(shù)據(jù)塊里。這里的00c0表示文件號：
SQL> select sys.pkg_number_trans.f_hex_to_dec('c')/4 file# FROM dual;
FILE#
----------
3
SQL> select sys.pkg_number_trans.f_hex_to_dec('1ce4') as blk# FROM dual;
BLK#
----------------------
7396
因此這20條記錄在3號數(shù)據(jù)文件的7396號數(shù)據(jù)塊里。我們可以使用dbms_rowid來驗證。
SQL> select distinct dbms_rowid.rowid_relative_fno(rowid) as file#,
2 dbms_rowid.rowid_block_number(rowid) as block#
3 from t_bitmap_test;
FILE# BLOCK#
---------- ----------
3 7396
可以看到，完全符合。
每個索引條目的“bitmap : (4)”部分表示的也就是前面說到的bit位了，由1、0組成。
按照前面bitmap的理論，這20條記錄所對應(yīng)的三個索引條目的bitmap的樣子應(yīng)該為：
Key_value start_rowid end_rowid 理論上的bitmap 轉(zhuǎn)儲文件的bitmap
1 00c01ce4.0 00c01ce4.0017 00100110000110000010 ca 64 18 04
2 00c01ce4.0 00c01ce4.0017 01000001010000110100 ca 82 c2 02
3 00c01ce4.0 00c01ce4.0017 10011000101001001001 ca 19 25 09
轉(zhuǎn)儲文件里的bitmap如何對應(yīng)到bit位呢 ？首先第一個字節(jié)的ca可以不考慮，暫時不知道第一個字節(jié)是什么意思。只考慮后三個字節(jié)。比如對于key_value=3來說，19，25，09對應(yīng)的二進制為：
SQL> col c1 format a10
SQL> col c2 format a10
SQL> col c3 format a10
SQL> select sys.pkg_number_trans.f_hex_to_bin(19) as c1,
2 sys.pkg_number_trans.f_hex_to_bin(25) as c2,
3 sys.pkg_number_trans.f_hex_to_bin(09) as c3 from dual;
C1 C2 C3
---------- ---------- ----------
11001 100101 1001
其中不足8位的前面用0補齊，因此，C1=00011001，C2=00100101，C3=00001001
在二進制里，每個應(yīng)該倒過來，從右到左排列，因此為：
C3 C2 C1
00001001 00100101 00011001
然后將它們組織為一個由多個bit位組成的bitmap的話，仍然從右到左，依次取出每個bit位，于是我們有：100110001010010010010000。我們可以把這個bit串與理論上的bitmap比較一下：
100110001010010010010000
10011000101001001001
很明顯，除了最后多出來的4個0以外，其余部分完全一致。而最后多出的0并不影響這個索引條目的使用。
類似的，我們可以使用相同的方法來依次驗證另外兩個鍵值，都是符合理論值的。
數(shù)據(jù)都在一個數(shù)據(jù)塊里的情況比較容易理解。如果被索引的數(shù)據(jù)分布在多個數(shù)據(jù)塊里呢？
經(jīng)常會有人問到，只記錄start rowid和end rowid，如果被索引的記錄分布在多個數(shù)據(jù)塊里，那么oracle如何根據(jù)start rowed來找到bitmap里的bit=1所對應(yīng)的記錄的rowid呢？
創(chuàng)建一個表：
SQL> create table t_bitmap_2(id number,bitcol char(2000));
insert into t_bitmap_2 values(1,'A');
insert into t_bitmap_2 values(2,'A');
insert into t_bitmap_2 values(3,'A');
insert into t_bitmap_2 values(4,'B');
insert into t_bitmap_2 values(5,'A');
insert into t_bitmap_2 values(6,'A');
insert into t_bitmap_2 values(7,'B');
insert into t_bitmap_2 values(8,'A');
insert into t_bitmap_2 values(9,'A');
insert into t_bitmap_2 values(9,'A');
insert into t_bitmap_2 values(10,'B');
insert into t_bitmap_2 values(11,'B');
insert into t_bitmap_2 values(12,'B');
insert into t_bitmap_2 values(13,'B');
insert into t_bitmap_2 values(14,'B');
insert into t_bitmap_2 values(15,'B');
COMMIT;
獲得這15條記錄所在的數(shù)據(jù)塊號：
SQL> select distinct dbms_rowid.rowid_relative_fno(rowid) as file#,
2 dbms_rowid.rowid_block_number(rowid) as block#
3 from t_bitmap_2;
FILE# BLOCK#
---------- ----------
3 7428
3 7429
3 7430
3 7431
3 7432
3 7433
可以知道，這15條記錄分布在6個數(shù)據(jù)塊里。
然后跟蹤對于bitcol列上的bitmap索引的創(chuàng)建過程：
alter session set events '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
……
srid=00c01d04.0 erid=00c01d08.7 bitmap: (11): c8 06 c0 44 f8 b3 01 07 f8 56 06
……
qerbiCon: 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 20
……
srid=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): c8 06 c0 44 f8 b3 01 07 f8 56 06
其數(shù)據(jù)塊從1d04到1d08，也就是：
SQL> select sys.pkg_number_trans.f_hex_to_dec('1d04') as s_blk#,
2 sys.pkg_number_trans.f_hex_to_dec('1d08') as e_blk#
3 from dual;
S_BLK# E_BLK#
---------- ----------
7428 7432
而鍵值B的索引條目為：
srid=00c01d04.0 erid=00c01d09.7 bitmap: (12): 00 f8 56 06 f8 56 07 c0 a1 01 c0 44
其數(shù)據(jù)塊從1d04到1d09，也就是：
SQL> select sys.pkg_number_trans.f_hex_to_dec('1d04') as s_blk#,
2 sys.pkg_number_trans.f_hex_to_dec('1d09') as e_blk#
3 from dual;
S_BLK# E_BLK#
---------- ----------
7428 7433
這個時候，
SQL> select substr(bitcol,1,1) as bitcol,dbms_rowid.rowid_block_number(rowid) as block# from t_bitmap_2;
BI BLOCK#
-- ----------
B 7428
A 7428
A 7428
A 7429
B 7429
B 7429
B 7430
B 7430
B 7430
A 7431
A 7431
A 7431
B 7432
A 7432
A 7432
B 7433
這時，oracle放了很多的bit來對應(yīng)這15條記錄，但是oracle如何根據(jù)這些bit位來找對應(yīng)的rowid就猜不出了。還希望各位牛人繼續(xù)補充。
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報。
