索引的深入研究OCP漫漫路途之bitmap

1、位图（bitmap）索引是另外一种索引类型，它的组织形式与B树索引相同，也是一棵平衡树。与B树索引的区别在于叶子节点里存放索引条目的方式不同。从前面我们知道，B树索引的叶子节点里，对于表里的每个数据行，如果被索引列的值不为空的，则会为该记录行在叶子节点里维护一个对应的索引条目。而位图索引则不是这样，其叶子节点里存放的索引条目如下图所示。      假设某个表T里所有的记录在列C1上只具有三个值：01、02和03。在表T的C1列上创建位图索引以后，则叶子节点的内容如图9-14所示。可以看到，位图索引只有三个索引条目，也就是每个C1列的值

2、对应一个索引条目。位图索引条目上还包含表里第一条记录所对应的ROWID以及最后一条记录所对应的ROWID。索引条目的最后一部分则是由多个bit位所组成的bitmap，每个bit位就对应一条记录。位图索引的结构      当发出where c1=01这样的SQL语句时，oracle会去搜索01所在的索引条目，然后扫描该索引条目中的bitmap里所有的bit位。第一个bit位为1，则说明第一条记录上的C1值为01，于是返回第一条记录所在的ROWID（根据该索引条目里记录的start ROWID加上行号得到该记录所在的ROWID）。第二个b

3、it位为0，则说明第二条记录上的C1值不为01，依此类推。另外，如果索引列为空，也会在位图索引里记录，也就是将对应的bit位设置为0即可。如果索引列上不同值的个数比较少的时候，比如对于性别列（男或女）等，则使用位图索引会比较好，因为它对空间的占用非常少（因为都是用bit位来表示表里的数据行），从而在扫描索引的时候，扫描的索引块的个数也比较少。可以试想一下，如果在列的不同值非常多的列上，比如主键列上，创建位图索引，则产生的索引条目就等于表里记录的条数，同时每个索引条目里的bitmap里，只有一个1，其它都是0。这样还不如B树索引的效率高。如果被索引的列经常被更新的话，则不适合使用位图索引。因为当

4、更新位图所在的列时，由于要在不同的索引条目之间修改bit位，比如将第一条记录从01变为02，则必须将01所在的索引条目的第一个bit位改为0，再将02所在的索引条目的第一个bit位改为1。因此，在更新索引条目的过程中，会锁定位图索引里多个索引条目。也就是同时只能有一个用户能够更新表T，从而降低了并发性。      位图索引比较适合用在数据仓库系统里，不适合用在OLTP系统里。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);索引已创建。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事件用来跟踪创建bitmap索引的过程。而TREEDUMP则用来转储索引的树状结构。打开转储出来的文件：* 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这一段是创建bitmap索引的过程。我们先把被

21、索引的列的值换算成十六进制：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对应的十六进制则是04、03、0

22、2。也就是上面转储部分显示的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=

23、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 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):  ca 64 18 04这里的srid表示start rowid，

25、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;   

26、60; FILE#-         3SQL> 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_

27、block_number(rowid) as block#  3  from t_bitmap_test;     FILE#     BLOCK#- -       3    7396可以看到，完全符合。每个索引条目的“bitmap : (4)”部分表示的也就是前面说到的bit位了，由1、0组成。按照前面bitmap的理论，这20条记录所对应的三个索引条目的bitmap的样子应该为：Key_value&#

28、160;   start_rowid    end_rowid      理论上的bitmap         转储文件的bitmap1          00c01ce4.0    00c01ce4.0017    ca 64 18 042   &

29、#160;      00c01ce4.0    00c01ce4.0017    ca 82 c2 023          00c01ce4.0    00c01ce4.0017    ca 19 25 09转储文件里的bitmap如何对应到bit位呢 ？首先第一个字节的ca可以不考虑，暂时不知道第一个字节是什么意思。只考虑后三个字节

30、。比如对于key_value=3来说，19，25，09对应的二进制为：SQL> col c1 format a10SQL> col c2 format a10SQL> col c3 format a10SQL> 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&

31、#160;        C2         C3- - -11001      100101     1001其中不足8位的前面用0补齐，因此，C1=00011001，C2=00100101，C3=00001001在二进制里，每个应该倒过来，从右到左排列，因此为：C3       &#

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

33、#160;      7428         3       7429         3       7430         3    

34、0;  7431         3       7432         3       7433可以知道，这15条记录分布在6个数据块里。然后跟踪对于bitcol列上的bitmap索引的创建过程：alter session set events '10608 trace name context

35、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=00c0

36、1d08.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和e

37、nd 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