BTREE与其它索引的优缺点对比

时间:2017-01-09  |  来源:cnphp6

数据库BTree索引、Hash索引、Bitmap位图索引的优缺点

 (2016-01-05 17:13:40)
标签: 

数据库

 

索引

 

mysql

 

oracle

分类: IT
http://www.devnote.cn/article/360.html
 
测试于:MySQL 5.5.25

当前测试的版本是Mysql 5.5.25只有BTree和Hash两种索引类型,默认为BTree。Oracle或其他类型数据库中会有Bitmap索引(位图索引),这里作为比较也一起提供。

 

BTree索引

BTree(多路搜索树,并不是二叉的)是一种常见的数据结构。使用BTree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。按照翻译,B 通常认为是Balance的简称。这个数据结构一般用于数据库的索引,综合效率较高。——百度百科

不适合:

  • 单列索引的列不能包含null的记录,复合索引的各个列不能包含同时为null的记录,否则会全表扫描;
  • 不适合键值较少的列(重复数据较多的列);
  • 前导模糊查询不能利用索引(like '%XX'或者like '%XX%')

 

Hash散列索引

Hash散列索引是根据HASH算法来构建的索引。虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些。

适合:

  • 精确查找非常快(包括= <> 和in),其检索效率非常高,索引的检索可以一次定位,不像BTree 索引需要从根节点到枝节点,所以 Hash 索引的查询效率要远高于 B-Tree 索引。

不适合:

  • 不适合模糊查询和范围查询(包括like,>,<,between……and等),由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系,并不能保证和Hash运算前完全一样;
  • 不适合排序,数据库无法利用索引的数据来提升排序性能,同样是因为Hash值的大小不确定;
  • 复合索引不能利用部分索引字段查询,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。
  • 同样不适合键值较少的列(重复值较多的列);

 

Bitmap位图索引

 就是用位图表示的索引,对列的每个键值建立一个位图。相对于BTree索引,占用的空间非常小,创建和使用非常快。位图索引由于只存储键值的起止Rowid和位图,占用的空间非常少。如test表中有state这样一列,10行数据如下:

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

适合

  • 适合决策支持系统;
  • 当select count(XX) 时,可以直接访问索引中一个位图就快速得出统计数据;
  • 当根据键值做and,or或 in(x,y,..)查询时,直接用索引的位图进行或运算,快速得出结果行数据。

不适合

  • 不适合键值较多的列(重复值较少的列);
  • 不适合update、insert、delete频繁的列,代价很高。

 

 

 
如过此内容对您有帮助,欢迎以点击广告的形式来支持我们,但请每天不要多于一次,否则可能被识别恶意点击,导致封号。