bitmap索引的深入研究

位图（bitmap）索引是另外一种索引类型，它的组织形式与B树索引相同，也是一棵平衡树。与B树索引的区别在于叶子节点里存放索引条目的方式不同。从前面我们知道，B树索引的叶子节点里，对于表里的每个数据行，如果被索引列的值不为空的，则会为该记录行在叶子节点里维护一个对应的索引条目。而位图索引则不是这样，其叶子节点里存放的索引条目如下图所示。假设某个表T里所有的记录在列C1上只具有三个值：01、02和03。在表T的C1列上创建位图索引以后，则叶子节点的内容如图9-14所示。可以看到，位图索引只有三个索引条目，也就是每个C1列的值对应一个索引条目。位图索引条目上还包含表里第一条记录所对应的ROWID以及最后一条记录所对应的ROWID。索引条目的最后一部分则是由多个bit位所组成的bitmap，每个bit位就对应一条记录。位图索引的结构当发出wherec1=’01’这样的SQL语句时，oracle会去搜索01所在的索引条目，然后扫描该索引条目中的bitmap里所有的bit位。第一个bit位为1，则说明第一条记录上的C1值为01，于是返回第一条记录所在的ROWID（根据该索引条目里记录的startROWID加上行号得到该记录所在的ROWID）。第二个bit位为0，则说明第二条记录上的C1值不为01，依此类推。另外，如果索引列为空，也会在位图索引里记录，也就是将对应的bit位设置为0即可。如果索引列上不同值的个数比较少的时候，比如对于性别列（男或女）等，则使用位图索引会比较好，因为它对空间的占用非常少（因为都是用bit位来表示表里的数据行），从而在扫描索引的时候，扫描的索引块的个数也比较少。可以试想一下，如果在列的不同值非常多的列上，比如主键列上，创建位图索引，则产生的索引条目就等于表里记录的条数，同时每个索引条目里的bitmap里，只有一个1，其它都是0。这样还不如B树索引的效率高。如果被索引的列经常被更新的话，则不适合使用位图索引。因为当更新位图所在的列时，由于要在不同的索引条目之间修改bit位，比如将第一条记录从01变为02，则必须将01所在的索引条目的第一个bit位改为0，再将02所在的索引条目的第一个bit位改为1。因此，在更新索引条目的过程中，会锁定位图索引里多个索引条目。也就是同时只能有一个用户能够更新表T，从而降低了并发性。位图索引比较适合用在数据仓库系统里，不适合用在OLTP系统里。SQLcreatetablet_bitmap_testas2selectrownumasid,trunc(dbms_random.value(1,4))asbitcol3fromdba_objectswhererownum=20;SQLselect*fromt_bitmap_test;IDBITCOL--------------------132231435361718293102113121131143152162173182191203SQLconnecthr/hr已连接。SQLaltersessionsetevents'10608tracenamecontextforever,level10';会话已更改。SQLcreatebitmapindexidx_t_bitmap_testont_bitmap_test(bitcol);索引已创建。SQLaltersessionsetevents'10608tracenamecontextoff';会话已更改。SQLselectobject_idfromuser_objectswhereobject_name='IDX_T_BITMAP_TEST';OBJECT_ID----------24499SQLaltersessionsetevents'immediatetracenameTREEDUMPlevel24499';会话已更改。10608事件用来跟踪创建bitmap索引的过程。而TREEDUMP则用来转储索引的树状结构。打开转储出来的文件：***SESSIONID:(7.13)2008-06-1014:33:46.000qerbiARwo:bitmapsizeis8168qerbiIPIdefaultpctfree=10qerbiIPIlength=0qerbiAllocatepfree=127space=8168qerbiStartfirststartqerbiRop:rid=00c01ce4.0000,new=Y,key:(2):c104qerbiCmpSznotfoundpctfree=10qerbiCmpSzadjblksize=7351length=0qerbiRopkeysize=4maxbm=3531kdibcoinit(3116714):srid=00c01ce4.0000qerbiRop:rid=00c01ce4.0001,new=Y,key:(2):c103kdibcoinit(3116698):srid=00c01ce4.0001qerbiRop:rid=00c01ce4.0002,new=Y,key:(2):c102kdibcoinit(311661c):srid=00c01ce4.0002qerbiRop:rid=00c01ce4.0003,new=N,key:(2):c104qerbiRop:rid=00c01ce4.0004,new=N,key:(2):c104qerbiRop:rid=00c01ce4.0005,new=N,key:(2):c102qerbiRop:rid=00c01ce4.0006,new=N,key:(2):c102qerbiRop:rid=00c01ce4.0007,new=N,key:(2):c103qerbiRop:rid=00c01ce4.0008,new=N,key:(2):c104qerbiRop:rid=00c01ce4.0009,new=N,key:(2):c103qerbiRop:rid=00c01ce4.000a,new=N,key:(2):c104qerbiRop:rid=00c01ce4.000b,new=N,key:(2):c102qerbiRop:rid=00c01ce4.000c,new=N,key:(2):c102qerbiRop:rid=00c01ce4.000d,new=N,key:(2):c104qerbiRop:rid=00c01ce4.000e,new=N,key:(2):c103qerbiRop:rid=00c01ce4.000f,new=N,key:(2):c103qerbiRop:rid=00c01ce4.0010,new=N,key:(2):c104qerbiRop:rid=00c01ce4.0011,new=N,key:(2):c103qerbiRop:rid=00c01ce4.0012,new=N,key:(2):c102qerbiRop:rid=00c01ce4.0013,new=N,key:(2):c104kdibcoend(3116714):erid=00c01ce4.0017status=3qerbiCon:key:(2):c104srid=00c01ce4.0erid=00c01ce4.17bitmap:(4):ca192509kdibcoend(3116698):erid=00c01ce4.0017status=3qerbiCon:key:(2):c103srid=00c01ce4.0erid=00c01ce4.17bitmap:(4):ca82c202kdibcoend(311661c):erid=00c01ce4.0017status=3qerbiCon:key:(2):c102srid=00c01ce4.0erid=00c01ce4.17bitmap:(4):ca641804这一段是创建bitmap索引的过程。我们先把被索引的列的值换算成十六进制：SQLselectdump(3),dump(2),dump(1)fromdual;DUMP(3)DUMP(2)DUMP(1)------------------------------------------------------Typ=2Len=2:193,4Typ=2Len=2:193,3Typ=2Len=2:193,24、3、2对应的十六进制则是04、03、02。也就是上面转储部分显示的key部分的键值。可以看到，oracle在创建bitmap索引时，先从第一条记录开始扫描，取出第一条记录的键值（bitcol=3），也就是“qerbiRop:rid=00c01ce4.0000,new=Y,key:(2):c104”。new=Y说明这是一个新的键值，因此会对应到一个索引条目。扫描第二条记录时，发现bitcol=2，该键值也是一个新的键值，因此产生一个新的索引条目，对应“qerbiRop:rid=00c01ce4.0001,new=Y,key:(2):c103”。扫描到第三条记录时，发现bitcol=1，该键值也是一个新的键值，因此产生第三个索引条目，对应“qerbiRop:rid=00c01ce4.0002,new=Y,key:(2):c102”。接下来扫描到的记录所对应的bitcol的值都是1、2、3中的一个，因此都不会产生新的索引条目，因此它们的new都为N。然后扫描完表里的所有记录以后，开始创建bitmap索引条目，也就是下面的部分：qerbiCon:key:(2):c104srid=00c01ce4.0erid=00c01ce4.17bitmap:(4):ca192509kdibcoend(3116698):erid=00c01ce4.0017status=3qerbiCon:key:(2):c103srid=00c01ce4.0erid=00c01ce4.17bitmap:(4):ca82c202kdibcoend(311661c):erid=00c01ce4.0017status=3qerbiCon:key:(2):c102srid=00c01ce4.0erid=00c01ce4.17bitmap:(4):ca641804这里的srid表示startrowid，erid表示endrowid。可以看到总共产生了3个索引条目，其key分别为：04、03、02。这3个索引条目的startrowid和endrowid的格式分两部分，中间用点隔开，点左边的表示文件号（从左边第一个字节开始的4个字节表示）和数据块号（从左边第五个字节开始的4个字节表示），点右边表示数据块里的行号。这里的显示可以看到，这20条记录都位于相同的数据块里。这里的00c0表示文件号：SQLselectsys.pkg_number_trans.f_hex_to_dec('c')/4file#FROMdual;FILE#----------3SQLselectsys.pkg_number_trans.f_hex_to_dec('1ce4')asblk#FROMdual;BLK#----------------------7396因此这20条记录在3号数据文件的7396号数据块里。我们可以使用dbms_rowid来验证。SQLselectdistinctdbms_rowid.rowid_relative_fno(rowid)asfile#,2dbms_rowid.rowid_block_number(rowid)asblock#3fromt_bitmap_test;FILE#BLOCK#--------------------37396可以看到，完全符合。每个索引条目的“bitmap:(4)”部分表示的也就是前面说到的bit位了，由1、0组成。按照前面bitmap的理论，这20条记录所对应的三个索引条目的bitmap的样子应该为：Key_valuestart_rowidend_rowid理论上的bitmap转储文