ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 位图索引(Bitmap Index)——从B*树索引到位图索引

位图索引(Bitmap Index)——从B*树索引到位图索引

原创 Linux操作系统 作者:realkid4 时间:2011-05-09 23:04:31 0 删除 编辑

 

索引是我们最常使用的一种性能优化手段。本质上讲,使用索引的优势就是通过付出一个额外的索引块扫描过程,获取到符合条件的rowid集合,之后依据rowid集合访问数据表块。从而节省下进行全表搜索的I/O消耗。

 

在各类型索引中,我们已经习惯使用的就是B*树索引,也就是将索引列的取值构建为一颗平衡二叉树。索引列每个非空行对应一个叶子节点,叶子节点上的内容包括索引取值和对应的rowidB*树的特点就是从根节点搜索到叶子节点,所经过的路径和消耗相同。

 

 

我们说B*树索引是目前数据库解决方案中普适性最好的一种索引类型。首先,B*索引适应各种类型数据库,可以支持目前海量数据库的大多数数据访问需求。其次,对一般选择性好的数据列,B*索引通常可以提供比较优秀的索引树访问执行计划。最后,以Index Range ScanIndex Unique ScanIndex Fast ScanIndex Skip Scan为主体的Index执行计划已经比较成熟,Oracle在处理此类问题上有很多独有的技术可以使用。

 

 

但是,随着数据分布和取值的一些特殊性,在一些场合下,B*树索引存在一些力不从心的现象。

 

ü        低基数数据列索引结构空间冗余。B*树结构中,索引列值和rowid都会保存在索引的叶子节点上。如果索引列的选择性差,只有少数的几个可选取值,那么在索引叶子节点上就是存在大量相邻相同键值的叶子节点。这样是一种严重的空间浪费和IO扫描浪费;

ü        单一索引路径选择。在通常的SQL条件中,常常包括多个条件列,这些条件列可能分别属于不同的多个索引。但是由于B*树索引的特殊性,我们的执行计划中只能出现一个索引的执行路径,其他列条件只能作为一种筛选条件出现。这样,很多付出维护成本的索引就失去了意义;

ü        Null值和OR条件的限制。传统的B*树索引,Null值是不会进入到索引结构的。同时对OR条件也存在很大的限制;

 

诸如此类,在一些情况下,B*树索引是存在限制的。而这些问题,可以考虑通过位图索引(Bitmap Index)来解决。

 

首先,位图索引也是一种和数据表分开存储的段segment结构,也是通过尽可能少读块block获取结果集合rowid来实现优化目的的对象。位图索引和B*树索引的相同点,在于都是将平衡树作为初始的结构。区别在于B*树索引的叶子节点对应的是每一个索引列的对应关系,而位图索引的每个叶子节点对应的是一种索引键值取值。每个位图索引的叶子节点上,包括三部分的内容:首先是键值取值,第二部分为rowid范围,最后为位图对应向量。

 

ü        Bitmap Index与传统的B*树结构最大的区别就是叶子节点的结构。对Bitmap Index来说,一个出现的索引列取值就对应着一个叶子节点。而B*树是一个数据行对应一个叶子节点。这样,也就意味着当索引列取值是低基数的时候,Bitmap Index结构要远远小于B*树索引结构;

ü        第二部分的rowid范围是用于进行偏移计算使用的。这部分记录索引列对应的数据行起始和结束的rowid取值范围;

ü        最后也是Bitmap的重中之重,就是位图向量。在Bitmap Index中,使用计算机最小的计数单位:位bit来表示行取值情况。每一个数据行对应一位bit 0/1取值,如果数据表有1000行,那么对应的向量就有1000位长度。针对某一位来说,如果对应行的取值和该向量所在叶子节点上对应索引取值相同,取值为1,否则为0

ü         

 

那么,我们已经可以初步考虑到Oraclebitmap Index的基本结构。一颗叶子节点很少的树(当列基数较小的时候,也就是列取值较小的时候),每个叶子节点对应一种可能的列取值。每个叶子节点上携带一个位图向量,表示所有行对应取值的信息。

 

 

下面,我们通过几个简单实验,看看Bitmap Index的创建和使用情况。

 

首先是环境准备:

 

//Oracle 11gR2上进行试验;

SQL> select * from v$version where rownum<2;

 

BANNER

--------------------------------------------------------------------------------

Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - Production

 

SQL> create table t as select object_id, owner, owner owner2 from dba_objects;

Table created

 

SQL> create index idx_t_owner on t(owner);

Index created

 

SQL> create bitmap index idx_t_ownerbit on t(owner2);

Index created

 

SQL> select count(distinct owner) from t;

 

COUNT(DISTINCTOWNER)

--------------------

                  30

 

SQL> select count(*) from t;

 

  COUNT(*)

----------

     72544

//构建一些空值

SQL> update t set wner=null, owner2=null where wner='ORDDATA';

248 rows updated

 

SQL> commit;

Commit complete

 

SQL> exec dbms_stats.gather_table_stats(user,'T',cascade => true);

PL/SQL procedure successfully completed

 

 

 

存储结构上比较

 

在存储结构上,数据表T包括超过7万行记录。对应的ownerowner2列取值完全一样,差异在于构建的索引结构上。我们检查一下两个索引段(Index Segment)的情况。

 

 

SQL> col segment_name for a15;

SQL> select segment_name, segment_type, bytes, extents, blocks from dba_segments where wner='SYS' and segment_name like 'IDX_T%';

 

SEGMENT_NAME    SEGMENT_TYPE       BYTES    EXTENTS     BLOCKS

--------------- ------------------ ---------- ---------- ----------

IDX_T_OWNER     INDEX                 2097152         17        256

IDX_T_OWNERBIT  INDEX                   65536          1          8

 

 

数据表相同、取值相同,不同索引类型的存储差异显而易见。普通索引使用空间大小超过2M,共使用17个分区extents,折合256block。而Bitmap Index所消耗的空间还没有超过初始对象分配的8个块block大小。所以,在适当的索引值下,Bitmap Index存储空间效率上有明显优势。

 

 

究其原因,也比较好理解。普通索引结构中,数据表增加一行,意味着要增加一个叶子节点。如果要超过原有的块容量,还要进行分支节点、叶子节点的拆分问题。而Bitmap Index只需要在所有的叶节点位图向量中增加一个bit位而已。

 

开篇我们提到过,索引的意义价值在于读尽可能少的数据块,获取到rowid列表后到数据表中定位。在获取数据集合相同的情况下,索引结构越小,带来的IO损耗就越少,进而成本就越低。这种特性对于数据海量的OLAPDataware系统来说,至关重要!

 

 

普通索引列条件

 

对索引搜索,Bitmap Index具有更高的执行成本优势。

 

//普通索引结构

SQL> select * from t where wner='SCOTT';

已选择36行。

已用时间:  00: 00: 00.01

 

执行计划

----------------------------------------------------------

Plan hash value: 1516787156

-------------------------------------------------------------------------------------------

| Id  | Operation           | Name        | Rows  | Bytes | Cost (%CPU)| Time     |

-------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT  |      |   103 |  1751 |     4   (0)| 00:00:01 |

|   1 |  TABLE ACCESS BY INDEX ROWID| T  |   103 |  1751 |     4   (0)| 00:00:01 |

|*  2 |   INDEX RANGE SCAN  | IDX_T_OWNER |   103 |   |     3   (0)| 00:00:01 |

-------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

   2 - access("OWNER"='SCOTT')

统计信息

----------------------------------------------------------

          1  recursive calls

          0  db block gets

         17  consistent gets

         11  physical reads

          0  redo size

       1013  bytes sent via SQL*Net to client

        398  bytes received via SQL*Net from client

          4  SQL*Net roundtrips to/from client

          0  sorts (memory)

          0  sorts (disk)

         36  rows processed

 

//Bitmap Index搜索路径

SQL> select * from t where owner2='SCOTT';

已选择36行。

 

已用时间:  00: 00: 00.01

执行计划

----------------------------------------------------------

Plan hash value: 2207144928

-----------------------------------------------------------------------------------------------

| Id  | Operation        | Name           | Rows  | Bytes | Cost (%CPU)| Time     |

-----------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT    |        |   103 |  1751 |    21   (0)| 00:00:01 |

|   1 |  TABLE ACCESS BY INDEX ROWID | T  |   103 |  1751 |    21   (0)| 00:00:01 |

|   2 |   BITMAP CONVERSION TO ROWIDS|      |       |       |            | |

|*  3 |    BITMAP INDEX SINGLE VALUE | IDX_T_OWNERBIT |       |       |  |  |

-----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

   3 - access("OWNER2"='SCOTT')

 

统计信息

----------------------------------------------------------

          1  recursive calls

          0  db block gets

         14  consistent gets

          2  physical reads

          0  redo size

       1013  bytes sent via SQL*Net to client

        398  bytes received via SQL*Net from client

          4  SQL*Net roundtrips to/from client

          0  sorts (memory)

          0  sorts (disk)

         36  rows processed

 

 

 

对比关系上,虽然两者实际执行时间接近,但是使用Bitmap Index的执行计划在IO处理量上具有比较明显的优势。

 

空值Null检索性

 

在准备数据环境时,我们已经有意的构建一部分null进入owner/owner2数据列。下面我们来看看实际的效果。

 

//普通索引列

SQL> explain plan for select * from t where owner is null;

 

Explained

 

SQL> select * from table(dbms_xplan.display);

 

PLAN_TABLE_OUTPUT

--------------------------------------------------------------------------------

Plan hash value: 1601196873

--------------------------------------------------------------------------

| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |

--------------------------------------------------------------------------

|   0 | SELECT STATEMENT  |      |   248 |  4216 |    60   (0)| 00:00:01 |

|*  1 |  TABLE ACCESS FULL| T    |   248 |  4216 |    60   (0)| 00:00:01 |

--------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

   1 - filter("OWNER" IS NULL)

13 rows selected

 

//Bitmap Index索引列

SQL> explain plan for select * from t where owner2 is null;

 

Explained

 

SQL> select * from table(dbms_xplan.display);

 

PLAN_TABLE_OUTPUT

--------------------------------------------------------------------------------

Plan hash value: 2207144928

--------------------------------------------------------------------------------

| Id  | Operation                    | Name           | Rows  | Bytes | Cost (%C

--------------------------------------------------------------------------------

|   0 | SELECT STATEMENT             |                |   248 |  4216 |    32

|   1 |  TABLE ACCESS BY INDEX ROWID | T              |   248 |  4216 |    32

|   2 |   BITMAP CONVERSION TO ROWIDS|                |       |       |

|*  3 |    BITMAP INDEX SINGLE VALUE | IDX_T_OWNERBIT |       |       |

--------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

   3 - access("OWNER2" IS NULL)

15 rows selected

 

 

可以看出,对Null来说,是不会进入普通的B*树,所以执行is null也就不可能出现索引路径。而null作为一个可选取值列值,是可以作为一个叶子节点出现在Bitmap Index上的。

 

 

结论:B*树索引在普适性上的优势,可以满足绝大多数的实际需求。但是一些特殊场景下,我们可以使用Bitmap索引来解决问题,提高数据表,特别是OLAP海量数据表的检索效率问题。

 

 

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

请登录后发表评论 登录
全部评论
求道~

注册时间:2010-11-30

  • 博文量
    545
  • 访问量
    7677888