当前位置：网站首页 > 技术博客 > 正文

位图索引原理

技术博客 来源： 网络 编辑：小编 发布时间：2024-12-06 17:30:05 浏览量：15



位图索引主要针对大量相同值的列而创建的索引。(例如：性别), 位图索引相对于传统的B树索引，在叶子节点上采用了完全不同的结构组织方式。传统B树索引将每一行记录保存为一个叶子节点，上面记录对应的索引列取值和行rowid信息。而位图索引将每个可能的索引取值组织为一个叶子节点。每个位图索引的叶子节点上，记录着索引键值、该索引键值的起始截止rowid和一个位图向量串。从本质上将，位图索引通过一个bit位来记录一个数据行是否存在对应键值。这种方式存储数据,相对于BTree索引,占用的空间非常小,创建和使用非常快. 这样做对比传统的B树索引空间节省高。而且可以借助计算机位图运算的快速特性来提高索引结果利用率。

位图索引(bitmap index)技术是一类特殊的数据库索引技术，其索引使用bit数组（或称bitmap、bit set、bit string、bit vector）进行存储与计算操作。

位图索引是从oracle 7.3版本开始引入的。目前oracle企业版和个人版都支持位图索引，但是标准版不支持。位图索引是这样一种结构，其中用一个索引键条目存储指向多行的指针，这与B树结构不同，在b树结构中，索引键和表中的行存在着对应关系。在位图索引中，可能只有很少的索引条目，每个索引条目指向多行，而在传统的B*树中，一个索引条目就指向一行那么什么是位图索引呢？（借用网络的例子讲解）

有张表名为table的表，由三列组成，分别是姓名、性别和婚姻状况，其中性别只有男和女两项，婚姻状况由已婚、未婚、离婚这三项，该表共有100w个记录。现在有这样的查询：

 


  姓名(Name)性别(Gender)婚姻状况(Marital)张三男已婚李四女已婚王五男未婚赵六女离婚孙七女未婚 

 

     
 
  1. 不使用索引
    2.  

 

不使用索引时，数据库只能一行行扫描所有记录，然后判断该记录是否满足查询条件。
 

     
 
  1. B树索引
    2.  

 

对于性别，可取值的范围只有’男’,‘女’，并且男和女可能各站该表的50%的数据，这时添加B树索引还是需要取出一半的数据， 因此完全没有必要。相反，如果某个字段的取值范围很广，几乎没有重复，比如身份证号，此时使用B树索引较为合适。事实上，当取出的行数据占用表中大部分的数据时，即使添加了B树索引，数据库如oracle、mysql也不会使用B树索引，很有可能还是一行行全部扫描。
 

     
 
  1. 位图索引
    2.  

 

位图索引创建了之后，生成是位图数据可以这么理解，比如，男女两种，然后一共八条数据，那么就生产两个字符串，一个代表男，一个代表女，字符串长度为数据的总数量，字符串的值：第一位（如果第一条数据是男那么就是1，如果不是就0），第二位，第三位，往后都是这样。由此就生成了长度为总数量，只包含01的字符串，通过这个字符串就能知道第几条数据是男，第几条不是男，同理，另外一条代表女的字符串也一样，是女的就1，不是女的就0。
 

如果等等。要为这些基数值比较小的列建索引，就需要建立位图索引。
 

对于性别这个列，位图索引形成两个向量，男向量为10100…，向量的每一位表示该行是否是男，如果是则位1，否为0，同理，女向量位01011。
 


  RowId12345…男10100女01011 

 

对于婚姻状况这一列，位图索引生成三个向量，已婚为11000…，未婚为00100…，离婚为00010…。
 


  RowId12345…已婚11000未婚00101离婚00010 

 

当我们使用查询语句“select * from table where Gender=‘男’ and Marital=“未婚”;”的时候 首先取出男向量10100…，然后取出未婚向量00100…，将两个向量做and操作，这时生成新向量00100…，可以发现第三位为1，表示该表的第三行数据就是我们需要查询的结果。
 

当我们使用查询语句“select * from table where Gender=‘男’ and Marital=“未婚”;”的时候 首先取出男向量10100…，然后取出未婚向量00100…，将两个向量做and操作，这时生成新向量00100…，可以发现第三位为1，表示该表的第三行数据就是我们需要查询的结果。
 


  RowId12345男10100and未婚00101结果00100 

 

创建语法很简单,就是在普通索引创建的语法中index前加关键字bitmap即可,例如:
 

 

在这里插入图片描述
 

     
 
  1. 索引块的一个索引行中存储键值、起止Rowid,以及这些键值的位置编码,
    2.  
 
  2. 位置编码中的每一位表示键值对应的数据行的有无.位数=表的总记录数
    3.  
 
  3. 所需的位图个数=索引列的不同键值多少,列的不同值越少,所需的位图就越少
    4.  
 
  4. 当根据键值查询时,可以根据起始Rowid和位图状态,快速定位数据.
    5.  
 
  5. 这样与B*树那样直接保存rowid的区别就在于每次都要进行rowid的换算工作。
    6.  

 

 

 

 

在这里插入图片描述
 

 

 

在这里插入图片描述
 

在该索引图中，共用5 类JOB，每类JOB 对应14 个比特位（对应14 行记录），其中某行的在该列的值与JOB 值对应则使用比特1 表示，如JOB = ‘CLERK’，第一行在该列对应的值是CLERK，就用比特1表示。否则用比特0表示，其他JOB类类似。
 

在这里插入图片描述
 

 

通过位图索引扫描JOB=‘CLERK’对应的位图记录，找到值为1 的行记录，即找到需要查找数据。
 

上述查询语句的目的是在EMP表中查询工作岗位是SALESMAN的员工的员工号，姓名和薪水，此时假设已经在EMP表的JOB列建立了位图索引，其结构如下图所示。
 

在这里插入图片描述
 

 

Bitmap测试
 

用实验说明为什么位图索引不适合OLTP，比较适合OLAP。即：DML操作比较多的表不适合使用位图索引。
 

 

以上面的EMP表为例，我们已经在该表的JOB字段建立了位图索引
 

 

在这里插入图片描述
 

 

在这里插入图片描述
 

 

可以看见10阻塞了128 。尽管他们修改的不是同一列。
 

在这里插入图片描述
 

Session1提交
 

在这里插入图片描述
 

Session2 阻塞解除，自动执行了
 

在这里插入图片描述
 

相对于B*Tree索引,位图索引由于只存储键值的起止Rowid和位图,占用的空间非常少. bitmap的空间占用主要与以下因素相关:
 

     
 
  1. 表的总记录数
    2.  
 
  2. 索引列的键值多少,列的不同值越少,所需的位图就越少.
    3.  

 

位图索引创建时不需要排序, B*Tree索引则在创建时需要排序,定位等操作,速度要慢得多.
 

Bitmap索引允许键值为空 B*Tree索引由于不记录空值,当基于is null的查询时,会使用全表扫描, 而对位图索引列进行is null查询时,则可以使用索引.
 

当使用count(XX),可以直接访问索引就快速得出统计数据.
 

当根据位图索引的列进行and,or或 in(x,y,…)查询时,直接用索引的位图进行或运算,在访问数据之前可事先过滤数据.
 

由于通过位图反映数据情况,批量操作时对索引的更新速度比B*Tree索引一行一行的处理快得多.
 

对于B*Tree索引,insert操作不会锁定其它会话的DML操作. 而位图索引,由于用位图反映数据,不同会话更新相同键值的同一位图段,insert、update、delete相互操作都会发锁定。
 

     
 
  1. 位图索引适合只有几个固定值的列，如性别、婚姻状况、行政区等等，而身份证号这种类型不适合用位图索引，如果用户查询的列的相异基数非常的小， 要为这些相异基数值比较小的列建索引，就需要建立位图索引。
    2.  

 

那么何谓相异基数非常的小？可以认为行集中不同项的个数除以行数应该是一个很小的数（接近0），例如，某个列（性别）可能取值为M、F、null.如果一个表中有20000条数据，那么3/20000=0.00015，那么这就算是个相异基数很小的情况，类似的，如果有个不同的值，与条结果相比，比值是0.01，同样也很小，也可以认为是相异基数很小的情况，都可以建立位图索引；
 

     
 
  1. 这个时候有人会说使用位图索引，因为busy只有两个值。好，我们使用位图索引索引busy字段！假设用户A使用update更新某个机器的busy值，比如update table set table.busy=1 where rowid=100;，但还没有commit，而用户B也使用update更新另一个机器的busy值，update table set table.busy=1 where rowid=12; 这个时候用户B怎么也更新不了，需要等待用户A commit。
    2.  

 

原因：用户A更新了某个机器的busy值为1，会导致所有busy为1的机器的位图向量发生改变，因此数据库会将busy＝1的所有行锁定，只有commit之后才解锁。
 

位图索引在读密集的环境中能很好地工作，但是对于写密集的环境则极不适合，原因在于，一个位图索引键条目（可以理解为前面的男 、女、未婚、已婚等）指向多行。如果一个会话修改了有索引的列的数据，那么大多数情况下，这个索引条目只想的所有行都会被锁定。oracle无法锁定一个位图索引条目中的单独一位，而是会锁定整个位图索引条目，倘若其他会话修改也需要更新同样的这个位图索引条目，就会被“关在门外”，这样就大大影响了并发性，因为每个更新都有可能锁定数百行，不允许并发地更新他们的位图列；
 

举个例子说明：有这样一个字段job，记录各个员工的职位如：dba 、java、php等等 ，假设我们在这个job列上建立了位图索引。假如rowid=100的员工职业为php,rowid=120的员工职业为php;
 

如果会话1使用update更新某个员工的职位（job），比如update table set table.job=‘dba’ where rowid=100;，但还没有commit，而会话2也使用update更新另一个员工的职位，update table set table.job=‘dba’ where rowid=120; 这个时候会话2怎么也更新不了，需要等待会话1 commit。
 

原因：会话1更新rowid=100的这个员工的职位，假如这个员工原来是php,现在改成dba,那么在commit之前，就会锁定所有job=php和job=dba的所有行，所以当会话2尝试更新job=dba只能等待锁，只有commit之后才解锁。这样就大大影响了并发性；
 

位图索引是为数据仓库（也就是查询环境设计的），位图索引特别不适合OLTP系统，位图索引不适合与dml频繁的环境，位图索引适用于DSS系统，位图索引不适合频繁修改的系统，弊端是严重影响
 

并发性，因为update索引列值的时候，会锁定新值和旧值指向的所有数据行，所以使用位图索引需慎重。

                            


                            

                                
  • 
                                    
                                    上一篇：
                                    
                                    java中内部类的定义
                                    
                                    
                                
    • 
                                
  • 
                                    
                                    下一篇：
                                    
                                    引用类型和基本数据类型有什么区别
                                    
                                    
                                
    • 
                            
    

                            
                            
    
                                
    
                                    版权声明：
    
                                    本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

    
                                    
    本文网址：https://www.mushiming.com/mjsbk/2815.html
    
                                
    
                            
    
                            
                        
    
                        
    
                            
    

                            
    
                        
    

                        
                        
                        
    
                            
    相关文章：
    
                            
                            
                        
                        
  • 
                                java中内部类的定义2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                usb写入保护工具2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                js获取class选择器2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                什么是余弦相似性2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                es6常用特性2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                引用类型和基本数据类型有什么区别2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                redis集群模式原理2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                java课程设计总结与思考2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                socks5代理服务器搭建2024-12-06 17:30:05
                        
    • 
                        
                        
  • 
                                玄幻:开局获得机缘抢夺系统2024-12-06 17:30:05
                        
    •