bitmap索引的深入研究

标签: bitmap 索引 研究 | 发表时间:2014-03-08 14:59 | 作者:czmmiao
出处:http://www.iteye.com

位图(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#
----------
         3

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(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        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来对应这15条记录,但是oracle如何根据这些bit位来找对应的rowid就猜不出了。还希望各位牛人继续补充。

 

参考至:http://blog.itpub.net/9842/viewspace-343286/

如有错误,欢迎指正

邮箱:[email protected]



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [bitmap 索引 研究] 推荐:

bitmap索引的深入研究

- - 数据库 - ITeye博客
位图(bitmap)索引是另外一种索引类型,它的组织形式与B树索引相同,也是一棵平衡树. 与B树索引的区别在于叶子节点里存放索引条目的方式不同. 从前面我们知道,B树索引的叶子节点里,对于表里的每个数据行,如果被索引列的值不为空的,则会为该记录行在叶子节点里维护一个对应的索引条目. 而位图索引则不是这样,其叶子节点里存放的索引条目如下图所示.

Bitmap优化

- - CSDN博客推荐文章
一个进程的内存可以由2个部分组成:. dalvik就是我们平常说的. java堆,我们创建的对象是在这里面分配的,而. Java后,以后这块内存即使释放后,也只能给. Java突然占用了一个大块内存,. malloc进行内存分配的,占用的是. C的内存,这个也就说明了,上述的. 4MBitmap无法生成的原因,.

Bitmap的秘密

- - 博客园_知识库
  之前已经参加过几次QCon峰会,不过今年QCon 2014 上海峰会对我来说比较特别,不再只是一名听众,而是第一次登台演讲. 感觉的确不太一样,一来是身份从听众变成了讲师,二来是因为成了讲师,让我接触到更多的业内朋友,也遇到了更多的提问、咨询. 会后已经有一段时间了,还有朋友提出想了解更多的技术知识.

Bitmap算法原理

- - 互联网旁观者
【什么是 Bit-map 】. 所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素. 由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省. 如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复).

bitmap算法简介

- - CSDN博客推荐文章
今天看到海量数据处理算法————bitmap(又称为bitset, 或者bit array), 有意思的算法. C++ 有一个头文件是. bitmap的思想就是数据压缩. 用一个二进制bit(0或者1)去标记某个元素对应的value, 这就是bit + map啊. 由于使用bit单位存储数据, 所以可大大节省内存空间.

Redis中bitmap的妙用

- - IT瘾-tuicool
在Redis中我们经常用到set,get等命令,细心的你有没有发现,还有几个相似的命令叫setbit,getbit,它们是用来干嘛的. 就是通过一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身. 我们知道8个bit可以组成一个Byte,所以bitmap本身会极大的节省储存空间.

AndroidのBitmap之大图片优化

- - 博客园_首页
不解释大家懂得,在listview 或grid或viewpager等大量大尺寸图片时,会造成OOM. 这里是优化图片内存的一个方法,注释写的很 明确... public Bitmap getBitmapFromNet(final String url,final int width,final int height){//从网络下载图片.

redis 用setbit(bitmap)统计活跃用户

- - 编程语言 - ITeye博客
Redis支持对String类型的value进行基于二进制位的置位操作. 通过将一个用户的id对应value上的一位,通过对活跃用户对应的位进行置位,就能够用一个value记录所有活跃用户的信息. 如下图所未,下图中的bitmap有9个位被置为1,表示这9个位上对应的用户是今天的活跃用户. 其中第15位表示uid为15的用户,第一位表示uid为0的用户.

研究生常用的18学术搜索引擎

- - 互联网分析
“深度搜”目前已收录4万种权威中英文学术期刊杂志,8千多万中英文学术论文、文献,. 主要集中在自然科学,社会科学,医疗卫生及知识产权领域. 对搜索内容在不同层次,以不同组合进行匹配,最相关的结果总是排列在最前面. 高质量内容:收集全世界绝大多数中英文权威学术期刊4万种,共8千多万篇学术论文. 英文出版商:Reed Elsevier, Springer, Wiley InterScience, Taylor and Francis, SAGE,.

xUtils 1.6.6 (Android工具库) 发布 - Bitmap模块优化

- - 开源中国社区最新新闻
感谢关注xUitls的网友最近一段时间给予的热心反馈,xUtils近期在bitmap模块进行了很多优化,同时修复和优化了大家反馈的一些问题.         更多介绍,源码和示例代码下载:https://github.com/wyouflf/xUtils.         详细更新记录见:https://github.com/wyouflf/xUtils/commits/master.