B树索引、位图索引和散列索引

约定不等于承诺〃 2022-07-17 00:29 293阅读 0赞

http://zhuyuehua.iteye.com/blog/1910602

索引在数据结构上可以分为三种B树索引、位图索引和散列索引

B树索引

结构：

![点击查看原始大小图片][1ef3a7d9-ecb9-35bc-8ca0-8ad9be186206.jpg]

特点：

1.索引不存储null值。

更准确的说，单列索引不存储null值，复合索引不存储全为ｎｕｌｌ的值

索引不能存储Null，所以对这列采用is null条件时，因为索引上根本没Null值，不能利用到索引，只

能全表扫描。

为什么索引列不能存Null值呢？将索引列值进行建树，其中必然涉及到诸多的比较操作。Null值

的特殊性就在于参与的运算大多取值为null。这样的话，null值实际上是不能参与进建索引的

过程。也就是说，null值不会像其他取值一样出现在索引树的叶子节点上。

B树索引测试1：NULL是否存在索引上。

create table btree\_test(id number,code varchar2(10));

create index idx\_btree\_test\_id on btree\_test(id,code);

select object\_id from user\_objects where object\_name='IDX\_BTREE\_TEST\_ID';

alter session set events 'immediate trace name treedump level 59097';

insert into btree\_test values(null,null);

alter session set events 'immediate trace name treedump level 59097';

insert into btree\_test values(null,'1');

alter session set events 'immediate trace name treedump level 59097';

insert into btree\_test values(1,null);

alter session set events 'immediate trace name treedump level 59097';

然后查看转储文件，admin\\数据库名\\udump

发现这样的信息：

\*\*\* 2013-07-19 14:56:41.827

\----- begin tree dump

leaf: 0x140142c 20976684 (0: nrow: 0 rrow: 0)

\----- end tree dump

\*\*\* 2013-07-19 14:56:54.480

\----- begin tree dump

leaf: 0x140142c 20976684 (0: nrow: 1 rrow: 1)

\----- end tree dump

\*\*\* 2013-07-19 14:57:08.139

\----- begin tree dump

leaf: 0x140142c 20976684 (0: nrow: 2 rrow: 2)

\----- end tree dump

nrow当前节点所含索引条目的数量（包括delete的条目）

rrow有效的索引条目的数量

可以发现：

插入null,null时，有效的索引条目为0

插入null,1时， 有效的索引条目为1

插入1,null时， 有效的索引条目为2

所以，复合索引只有当要插入的值全为Null时才不能放入存入索引中。

也可以这样看：

SELECT num\_rows FROM user\_indexes t WHERE t.index\_name ='btree\_test';

2.不适合键值较少的列（重复数据较多的列）。

假如索引列TYPE有5个键值，如果有1万条数据，那么 WHERE TYPE = 1将访问表中的2000个数据块。

再加上访问索引块，一共要访问大于200个的数据块。

如果全表扫描，假设10条数据一个数据块，那么只需访问1000个数据块，既然全表扫描访问的数据块

少一些，肯定就不会利用索引了。

3.前导模糊查询不能利用索引(like '%XX'或者like '%XX%')

假如有这样一列code的值为'AAA','AAB','BAA','BAB' ,如果where code like '%AB'条件，由于前面是

模糊的，所以不能利用索引的顺序，必须一个个去找，看是否满足条件。这样会导致全索引扫描或者全表扫

描。如果是这样的条件where code like 'A % '，就可以查找CODE中A开头的CODE的位置，当碰到B开头的

数据时，就可以停止查找了，因为后面的数据一定不满足要求。这样就可以利用索引了。

位图索引

就是用位图表示的索引，对列的每个键值建立一个位图。

如test表中有state这样一列，数据如下：

10 20 30 20 10 30 10 30 20 30

那么会建立三个位图，如下：

BLOCK1 KEY=10 1 0 0 0 1 0 1 0 0 0

BLOCK2 KEY=20 1 0 0 0 1 0 1 0 0 0

BLOCK3 KEY=30 1 0 0 0 1 0 1 0 0 0

位图索引特点：

1.相对于B\*Tree索引,占用的空间非常小,创建和使用非常快。

位图索引由于只存储键值的起止Rowid和位图,占用的空间非常少。

2.不适合键值较多的列。

3.不适合update、insert、delete频繁的列。

4.可以存储null值。

B\*Tree索引由于不记录空值,当基于is null的查询时,会使用全表扫描,而对位图索引列进

行is null查询时,则可以使用索引。

5.当select count(XX) 时,可以直接访问索引中一个位图就快速得出统计数据。

6.当根据键值做and,or或 in(x,y,..)查询时,直接用索引的位图进行或运算,快速得出结果行数

据。

位图测试1：位图索引查询效率（省略）。

位图测试2：修改数据时锁的范围。

create table test\_bitmap(id number,state number);

insert into test\_bitmap values (1,10);

insert into test\_bitmap values (2,10);

insert into test\_bitmap values (3,20);

insert into test\_bitmap values (4,20);

insert into test\_bitmap values (5,10);

insert into test\_bitmap values (6,30);

insert into test\_bitmap values (7,30);

insert into test\_bitmap values (8,20);

insert into test\_bitmap values (9,30);

insert into test\_bitmap values (10,20);

CREATE BITMAP INDEX INDEX\_TESTBITMAP\_STATE ON TEST\_BITMAP(STATE);

开一个PLSQL窗口（SESSION1），执行

update test\_bitmap set state = 20 where id = 1;

另开一个PLSQL窗口（SESSION2），执行

update test\_bitmap set state = 20 where id = 2;

或者

update test\_bitmap set state = 10 where id = 4;

可以发现，状态为20的所有行被锁定。

散列索引

散列索引是根据HASH算法来构建的索引，所以检索速度很快，但不能范围查询。

散列索引的特点

1.只适合等值查询（包括= <> 和in），不适合模糊或范围查询

[1ef3a7d9-ecb9-35bc-8ca0-8ad9be186206.jpg]: /images/20220717/acffe0b804d6465aa260f390a3465e2b.png

B树索引、位图索引和散列索引

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Hash索引和B+树索引的区别

相关 B树索引

相关数据结构与索引-- B+树索引

相关 innodb 04 索引-B+树索引

相关 B树索引、位图索引和散列索引

相关 [Oracle]B-树索引与位图索引

相关 B树索引+B树索引逻辑结构图+B树索引是怎么搜索数据+创建B树索引

相关 [ 数据库索引 ] B树和B+树

相关 [数据库] 索引 - B+树和哈希索引

相关 B+树索引和哈希索引的区别