ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 关于位图索引的split及bitmap to rowid实现问题

关于位图索引的split及bitmap to rowid实现问题

原创 Linux操作系统 作者:tolywang 时间:2011-02-22 17:52:02 0 删除 编辑
下面是参考网络上一些文档整理的bitmap的资料(部分),


Key     start_rowid       end_rowid          理论上的bitmap             转储文件的bitmap
<01     00c01ce4.0    00c01ce4.0017   00100110000110000010 >    ca 64 18 04
<02     00c01ce4.0    00c01ce4.0017   01000001010000110100 >    ca 82 c2 02
<03     00c01ce4.0    00c01ce4.0017   10011000101001001001 >    ca 19 25 09

其实dump出来的start-rowid及end-rowid分别如 srid=00c01ce4.0  erid=00c01ce4.17,左边的表示文件号(从左边第一个字节开始的4个字节表示)和数据块号(从左边第五个字节开始的4个字节表示),点右边表示数据块里的行号。

bitmap字符长度与start-rowid和end-rowid之间包含的rowid数量(表的数据行)一样,每个块的大小是8192*8bit*90%*87%(如果数据块大小为8K,pctfree=10%, 块头部占用一些),那么一个bitmap索引的叶子节点大概能索引51314 条记录

bitmap中没有直接记录rowid, 而是记录了一个位图, 位图中的每一个bit位都对应一个rowid, 之间有转换关系的.所以用bitmap索引的时候你可以在执行计划里看到 bitmap to rowid 这样的步骤.   

当我们发出where c1='01'这样的SQL时,oracle会搜索01所在的索引条目,然后扫描该索引条目中的bitmap里的所有bit位。第一个bit位是1,表示第一条上的c1的值是01,于是返回第一条记录所在的rowid(根据该索引条目里记录的start rowid加上行号得到该记录所在的rowid), 第二个bit位为0, 则说明第二条记录上的c1值不为01,依此类推。特别注意,如果索引列为空,也会在位图索引中记录,对应的bit位为0 ;



关于bitmap索引, 还有以下一些疑问:

1.   bitmap to rowid  是在SQL执行过程中的一个步骤,  假设列中的 01 值对应的位图 001010010 ,   SQL查询条件where col='01' ,
      据该索引条目里记录的start rowid加上行号得到该记录所在的rowid ,  从位图中可以看出对应的 3,5,8 行记录符合条件, 如果出现
      3,5,8 行的记录分别在两个不同的索引块中,  那么 start_rowid + 所在块中的行号 是如何找到的 ?   也就是说 “所在块中的行号”
      应该是参照 start_rowid 的值, 和在哪个块中没有关系 ?   

2.   在查看dump出来的start_rowid 值的时候,start_rowid存在不同的情况,这也就是说问题1中的“块中行号”是参考start_rowid 不是
      太准确, 应该是参照各自的start_rowid  .  不知道这样理解是否正确。

3.   一个bitmap索引的叶子节点大概能索引51314 条记录(8k block size),假设一个表列gender仅有'M','F' 值, 类似B-Tree,根节点
      存放两个索引条目  M  B1,  F   B2 (B1,B2表示branch地址),  B1 分支节点中存放M  L1, M  L2, M  L3 (L1等表示叶子节点地址),
      B2 分支节点存放  F  L4, F  L5, F  L6  等, 假设存放M的叶子节点L1中bitmap 是 00001000010010000010010100001001001
      00010100100101000000010100000000000000011111000000000 ...... 直到满为止, L2 同样000100011100....,  那么在
      进行查询动作时, L1, L2, L3 中的bitmap会被首尾组合起来进行运算 ?    如果记录足够多, 导致分支节点B1中空间不足,需要进行
      split ,  这里不存在类似b-tree中“插入的值”是最大值还是中间值的情况,都相等,比如是M,   那么B1中的索引条目会分出一半给新的
      分支节点 ?

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/35489/viewspace-687725/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
Oracle , MySQL, SAP IQ, SAP HANA, PostgreSQL, Tableau 技术讨论,希望在这里一起分享知识,讨论技术,畅谈人生 。

注册时间:2007-12-10

  • 博文量
    5595
  • 访问量
    13472039