bitmap索引的深入研究

位圖（bitmap）索引是另外一種索引類型，它的組織形式與B樹索引相同，也是一棵平衡樹。與B樹索引的差別在于葉子節點裡存放索引條目的方式不同。從前面我們知道，B樹索引的葉子節點裡，對于表裡的每個資料行，如果被索引列的值不為空的，則會為該記錄行在葉子節點裡維護一個對應的索引條目。而位圖索引則不是這樣，其葉子節點裡存放的索引條目如下圖所示。

假設某個表T裡所有的記錄在列C1上隻具有三個值：01、02和03。在表T的C1列上建立位圖索引以後，則葉子節點的内容如圖9-14所示。可以看到，位圖索引隻有三個索引條目，也就是每個C1列的值對應一個索引條目。位圖索引條目上還包含表裡第一條記錄所對應的ROWID以及最後一條記錄所對應的ROWID。索引條目的最後一部分則是由多個bit位所組成的bitmap，每個bit位就對應一條記錄。

位圖索引的結構

當發出where c1=’01’這樣的SQL語句時，oracle會去搜尋01所在的索引條目，然後掃描該索引條目中的bitmap裡所有的bit位。第一個bit位為1，則說明第一條記錄上的C1值為01，于是傳回第一條記錄所在的ROWID（根據該索引條目裡記錄的start ROWID加上行号得到該記錄所在的ROWID）。第二個bit位為0，則說明第二條記錄上的C1值不為01，依此類推。另外，如果索引列為空，也會在位圖索引裡記錄，也就是将對應的bit位設定為0即可。如果索引列上不同值的個數比較少的時候，比如對于性别列（男或女）等，則使用位圖索引會比較好，因為它對空間的占用非常少（因為都是用bit位來表示表裡的資料行），進而在掃描索引的時候，掃描的索引塊的個數也比較少。可以試想一下，如果在列的不同值非常多的列上，比如主鍵列上，建立位圖索引，則産生的索引條目就等于表裡記錄的條數，同時每個索引條目裡的bitmap裡，隻有一個1，其它都是0。這樣還不如B樹索引的效率高。

如果被索引的列經常被更新的話，則不适合使用位圖索引。因為當更新位圖所在的列時，由于要在不同的索引條目之間修改bit位，比如将第一條記錄從01變為02，則必須将01所在的索引條目的第一個bit位改為0，再将02所在的索引條目的第一個bit位改為1。是以，在更新索引條目的過程中，會鎖定位圖索引裡多個索引條目。也就是同時隻能有一個使用者能夠更新表T，進而降低了并發性。

位圖索引比較适合用在資料倉庫系統裡，不适合用在OLTP系統裡。

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);

索引已建立。

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事件用來跟蹤建立bitmap索引的過程。而TREEDUMP則用來轉儲索引的樹狀結構。打開轉儲出來的檔案：

*** 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

這一段是建立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對應的十六進制則是04、03、02。也就是上面轉儲部分顯示的key部分的鍵值。

可以看到，oracle在建立bitmap索引時，先從第一條記錄開始掃描，取出第一條記錄的鍵值（bitcol=3），也就是“qerbiRop: rid=00c01ce4.0000, new=Y , key: (2): c1 04”。new=Y說明這是一個新的鍵值，是以會對應到一個索引條目。掃描第二條記錄時，發現bitcol=2，該鍵值也是一個新的鍵值，是以産生一個新的索引條目，對應“qerbiRop: rid=00c01ce4.0001, new=Y , key: (2): c1 03”。掃描到第三條記錄時，發現bitcol=1，該鍵值也是一個新的鍵值，是以産生第三個索引條目，對應“qerbiRop: rid=00c01ce4.0002, new=Y , key: (2): c1 02”。

接下來掃描到的記錄所對應的bitcol的值都是1、2、3中的一個，是以都不會産生新的索引條目，是以它們的new都為N。

然後掃描完表裡的所有記錄以後，開始建立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。

可以看到總共産生了3個索引條目，其key分别為：04、03、02。

這 3個索引條目的start rowid和end rowid的格式分兩部分，中間用點隔開，點左邊的表示檔案号（從左邊第一個位元組開始的4個位元組表示）和資料塊号（從左邊第五個位元組開始的4個位元組表示），點右邊表示資料塊裡的行号。這裡的顯示可以看到，這20條記錄都位于相同的資料塊裡。這裡的00c0表示檔案号：

SQL> select sys.pkg_number_trans.f_hex_to_dec('c')/4 file# FROM dual;

FILE#

----------

SQL> select sys.pkg_number_trans.f_hex_to_dec('1ce4') as blk# FROM dual;

BLK#

----------------------

7396

是以這20條記錄在3号資料檔案的7396号資料塊裡。我們可以使用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條記錄所對應的三個索引條目的bitmap的樣子應該為：

Key_value start_rowid end_rowid 理論上的bitmap 轉儲檔案的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

轉儲檔案裡的bitmap如何對應到bit位呢？首先第一個位元組的ca可以不考慮，暫時不知道第一個位元組是什麼意思。隻考慮後三個位元組。比如對于key_value=3來說，19，25，09對應的二進制為：

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

在二進制裡，每個應該倒過來，從右到左排列，是以為：

C3 C2 C1

00001001 00100101 00011001

然後将它們組織為一個由多個bit位組成的bitmap的話，仍然從右到左，依次取出每個bit位，于是我們有：100110001010010010010000。我們可以把這個bit串與理論上的bitmap比較一下：

100110001010010010010000

10011000101001001001

很明顯，除了最後多出來的4個0以外，其餘部分完全一緻。而最後多出的0并不影響這個索引條目的使用。

類似的，我們可以使用相同的方法來依次驗證另外兩個鍵值，都是符合理論值的。

資料都在一個資料塊裡的情況比較容易了解。如果被索引的資料分布在多個資料塊裡呢？

經常會有人問到，隻記錄start rowid和end rowid，如果被索引的記錄分布在多個資料塊裡，那麼oracle如何根據start rowed來找到bitmap裡的bit=1所對應的記錄的rowid呢？

建立一個表：

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(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條記錄所在的資料塊号：

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個資料塊裡。

然後跟蹤對于bitcol列上的bitmap索引的建立過程：

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';

從轉儲出來的檔案可以看到，最終形成了兩個索引條目：

……

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

其資料塊從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

其資料塊從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 7429

B 7429

B 7430

A 7431

B 7432

A 7432

B 7433

這時，oracle放了很多的bit來對應這15條記錄

bitmap索引的深入研究

繼續閱讀

set define off關閉替代變量功能

報錯：'mysql' 不是内部或外部指令，也不是可運作的程式或批處理檔案。

Linxu常用指令技巧彙總

ERROR 1 (HY000): Can't create/write to file '/tmp/#sql_4188_1.MYI' (Errcode: 28)

艱難安裝LDAP,SSL認證

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

MySQL的4種隔離級别？出現問題

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

登入plsql 報錯 the account is locked --使用者被鎖

sqlServer根據經緯查距離

SequoiaDB巨杉資料庫C++驅動概述