位图索引区别于传统B*树索引有两个结构特点:其一是叶子节点上是一个可能的索引列取值对应一个叶子节点。另一个就是叶子节点上通过一个位图向量表示对应行是否取定这个索引值。
使用位图向量记录对应行的取值情况不仅可以带来存储空间上的节省,而且可以借助计算机位图运算的快速特性来提高索引结果利用率。下面我们通过模拟情况来进行分析。
Bitmap Index模拟说明
假设存在数据表T,有两个数据列A和B,取值如下。
序号 |
A |
B |
1 |
L |
1 |
2 |
T |
2 |
3 |
L |
2 |
4 |
M |
1 |
对两个数据列A、B分别建立位图索引:idx_t_bita和idx_t_bitb。两个索引对应的存储逻辑结构如下:
Idx_t_bita索引结构,对应的是叶子节点:
索引键值 |
起始rowid |
结束rowid |
位图向量 |
L |
xxx |
ttt |
1010 |
T |
xxx |
ttt |
0100 |
M |
xxx |
ttt |
0001 |
Idx_t_bitb索引结构,对应的是叶子节点:
索引键值 |
起始rowid |
结束rowid |
位图向量 |
1 |
xxx |
ttt |
1001 |
2 |
xxx |
ttt |
0110 |
|
|
|
|
对查询“select * from t where b=1 and (a=’L’ or a=’M’)”
分析:位图索引使用方面,和B*索引有很大的不同。B*索引的使用,通常是从根节点开始,经过不断的分支节点比较到最近的符合条件叶子节点。通过叶子节点上的不断Scan操作,“扫描”出结果集合rowid。
而位图索引的工作方式截然不同。通过不同位图取值直接的位运算(与或),来获取到结果集合向量(计算出的结果)。
针对实例SQL,可以拆分成如下的操作:
1、a=’L’ or a=’M’
a=L:向量:1010
a=M:向量:0001
or操作的结果,就是两个向量的或操作:结果为1011。
2、结合b=1的向量
中间结果向量:1011
B=1:向量:1001
and操作的结果,1001。翻译过来就是第一和第四行是查询结果。
3、获取到结果rowid
目前知道了起始rowid和终止rowid,以及第一行和第四行为操作结果。可以通过试算的方法获取到结果集合rowid。
上面的操作演算过程,说明了两个问题:
位图索引是可以多索引共同合作操作的,不像B*树索引只有一个会加入结果集合;
位图索引的工作是通过位逻辑运算,非扫描操作;
实际试验
下面我们通过一系列的实验,来进一步观察结果。
实验环境构建
SQL> create table t as select owner owner1, object_type type1, owner owner2, object_type type2 from dba_objects;
Table created
SQL> desc t;
Name Type Nullable Default Comments
------ ------------ -------- ------- --------
OWNER1 VARCHAR2(30) Y
TYPE1 VARCHAR2(19) Y
OWNER2 VARCHAR2(30) Y
TYPE2 VARCHAR2(19) Y
SQL> create index idx_t_owner1 on t(owner1);
Index created
SQL> create index idx_t_type1 on t(type1);
Index created
SQL> create bitmap index idx_t_owner2bit on t(owner2);
Index created
SQL> create bitmap index idx_t_type2bit on t(type2);
Index created
SQL> exec dbms_stats.gather_table_stats(user,'T',cascade => true);
PL/SQL procedure successfully completed
常规索引实验
我们构建的环境中,字段和类型完全相同。区别就在于使用的索引类型差异。下面我们先进行常规索引实验。
//为防止影响执行计划,先禁用Bitmap Index
SQL> alter index idx_t_owner2bit unusable;
Index altered
SQL> alter index idx_t_type2bit unusable;
Index altered
SQL> set pagesize 1000;
SQL> set linesize 1000;
SQL> explain plan for select * from t where owner1='SCOTT' and type1='TABLE';
已解释。
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------
Plan hash value: 2154532428
--------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time|
--------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 28 | 2 (0)| 00:00:01 |
|* 1 | TABLE ACCESS BY INDEX ROWID| T | 1 | 28 | 2 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | IDX_T_OWNER1 | 28 | | 1 (0)| 00:00:01 |
--------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("TYPE1"='TABLE')
2 - access("OWNER1"='SCOTT')
已选择15行。
注意:owner1和type1上均有B*索引,而且均出现在where条件上。结果采用的Scan方式,而且只使用到了一个索引对象。
Bitmap Index索引实验
此次使用Bitmap Index列对应查询条件。
//索引处理
SQL> alter index idx_t_type2bit rebuild;
Index altered
SQL> alter index idx_t_owner2bit rebuild;
Index altered
SQL> alter index idx_t_owner1 unusable;
Index altered
SQL> alter index idx_t_type1 unusable;
Index altered
SQL> explain plan for select * from t where owner2='SCOTT' and type2='TABLE';
已解释。
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
-------------------------------------------------------------------------------------------------
Plan hash value: 244872826
------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 61 | 1708 | 13 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID | T | 61 | 1708 | 13 (0)| 00:00:01 |
| 2 | BITMAP CONVERSION TO ROWIDS| | | | | |
| 3 | BITMAP AND | | | | | |
|* 4 | BITMAP INDEX SINGLE VALUE| IDX_T_TYPE2BIT | | | | |
|* 5 | BITMAP INDEX SINGLE VALUE| IDX_T_OWNER2BIT | | | | |
------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("TYPE2"='TABLE')
5 - access("OWNER2"='SCOTT')
已选择18行。
在一个SQL中,两个Bitmap索引均使用到。
下面实验一个比较复杂的条件。
SQL> explain plan for select * from t where owner2='SCOTT' and (type2='TABLE' or type2='INDEX');
已解释。
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------
Plan hash value: 3499411373
-------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 122 | 3416 | 24 (5)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID | T | 122 | 3416 | 24 (5)| 00:00:01 |
| 2 | BITMAP CONVERSION TO ROWIDS | | | | | |
| 3 | BITMAP AND | | | | | |
|* 4 | BITMAP INDEX SINGLE VALUE | IDX_T_OWNER2BIT | | | | |
| 5 | BITMAP OR | | | | | |
|* 6 | BITMAP INDEX SINGLE VALUE| IDX_T_TYPE2BIT | | | | |
|* 7 | BITMAP INDEX SINGLE VALUE| IDX_T_TYPE2BIT | | | | |
-------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("OWNER2"='SCOTT')
6 - access("TYPE2"='INDEX')
7 - access("TYPE2"='TABLE')
已选择21行。
请注意Bitmap系列and和or操作,和我们在开篇中做的模拟计算如出一辙。
Bitmap Index是一种适应范围比较窄,但是特效针对性很强的索引类型。在一些场合下合适使用,可以带来出乎意料的效果。
相关推荐
可以看出,位图索引`leo_bm_t1_index`的空间占用远小于B*树索引`leo_bm_t2_bt_index`。 ```sql SQL> col segment_name for a20 SQL> select segment_name, bytes 2 from user_segments 3 where segment_type = '...
C# 实现位图算法(BitMap) 位图算法(BitMap)是一种高效的数据结构,主要用于快速查询和存储大规模数据。下面将详细介绍 C# 中如何实现位图算法(BitMap)。 什么是 BitMap BitMap 的基本思想就是用一个 bit 位...
### B-树索引与位图索引的深入解析 #### B-树索引概述 B-树索引是Oracle数据库中最常用的索引类型之一,它利用B-树的数据结构来组织索引项,以便快速查找数据。B-树是一种自平衡的树形数据结构,每个节点最多可以...
**位图索引**(Bitmap Index)是一种特殊类型的索引,它使用位图来表示数据。每个位对应数据库表中的一个特定值,如果某个记录包含这个值,那么相应的位就被设置为1,否则为0。例如,如果表中有100万行,有三个不同...
BitmapIndexInternal是一个深入探讨位图索引内部结构的主题。位图索引是Oracle数据库系统中的一种特殊索引类型,自Oracle 7.3版本引入,主要用于处理低基数(即具有少量不同值)的列,以及在数据修改量小或几乎没有...
在众多索引类型中,位图索引(Bitmap Index)是一种特殊类型的索引,主要用于低基数(low cardinality)字段,即字段中不同的值较少的情况。 例如,考虑一个员工信息表(如上文提到的表格),其中`GENDER`列只有两种...
在ITAS的三项关键技术中,我们重点研究位图索引压缩算法,并在本文中进行了详细的调查。 当前最新的位图索引编码方案包括:BBC,WAH,PLWAH,EWAH,PWAH,CONCISE,COMPAX,VLC,DF-WAH和VAL-WAH。 基于分段,分块...
Bitmap Index(位图索引)是一种特殊的索引类型,主要用于处理那些具有较低基数(即不同值的数量较少)的列。传统上,数据库系统如Oracle使用B-Tree索引来加速查询,但对于具有少量唯一值的列,B-Tree索引可能不是...
本文将深入探讨两种常见的索引结构:B树(Btree)和位图索引(Bitmap Index),并对比它们的特性和适用场景。 首先,我们来了解B树。B树是一种自平衡的多路搜索树,适用于大量数据的存储系统。它的每个节点可以有多...
3. **位图索引的适用场景**:位图索引最适合在数据仓库环境中,特别是当连接操作涉及大量数据且索引列具有较少的唯一值时。在事务处理系统或在线应用交易处理(OLTP)系统中,位图索引可能不是最佳选择,因为它们不...
2. **位图索引(Bitmap Index)** 位图索引主要用于低基数(非唯一或重复值多)的列,将每个值用一个位来表示,节省空间,适合在并集查询中使用。 3. **反向索引(Reverse Index)** 反向索引主要应用于长文本...
为提高压缩码的利用率,提出一种适用于列存储数据库的压缩位图索引技术。定义反转、合并等操作,将所有计算的输入值与输出值格式化为位向量形式。通过活跃度衡量索引中位向量的复杂度,并对压缩位向量进行直接计算,优化...
位图索引(Bitmap Index):位图索引主要用于低基数列,即列中值的种类相对较少的情况。每个可能的值对应一个位图,位图中的每一位表示一个行是否包含该值。位图索引在进行多值筛选时特别有效,可以进行快速的...
CREATE [UNIQUE] [BITMAP] INDEX <索引名> ON <表名> (<列名> …); ``` 这句命令用于创建新的索引,可选择是否创建唯一索引或位图索引,并指定索引的名称、所基于的表和列。 总的来说,Oracle数据库的索引是优化...
`,或者创建位图索引,如`CREATE BITMAP INDEX idx_bitm ON class (classno) TABLESPACE tablespace_name;`。对于唯一索引,可以使用`CREATE UNIQUE INDEX`语句,确保列中的数据唯一性。 此外,索引也可以与约束...
CREATE BITMAP INDEX index_name ON table_name (column1, column2, ...); ``` 索引创建后,可能需要对其进行修改或重命名。修改索引的名字可以使用`ALTER INDEX`语句,如: ```sql ALTER INDEX index_name1 ...
4. **位图索引(Bitmap index)**:位图索引用位图表示索引键值,适合于低选择性(很多行具有相同的键值)的列,特别适用于联接操作和复杂的逻辑条件。 5. **位图联接索引(Bitmap Join Index)**:为多列联接操作优化...
CREATE BITMAP INDEX index_name ON table_name (column_name); ``` 创建索引时需要考虑的因素包括: - **索引列的选择**:选择经常用于查询条件的列。 - **索引的数量**:过多的索引可能会导致插入、更新和删除...