Hash索引与BitMap索引

待我称王封你为后i 2021-11-17 06:42 430阅读 0赞

# Hash索引 #

## 概念 ##

hash index是基于哈希表实现的，只有精确匹配索引所有列的查询才会生效。对于每一行数据，存储引擎都会对所有的索引列计算一个hash code,并将的有的hash code存储在索引中，同时在哈希表中保存指向每个数据行的指针。  
在MySQL中，只有Memory引擎显示支持哈希索引，也是默认索引类型。  
比如

create table test_hash(
    fname varchar(50) not null,
    lname varchar(50) not null,
    key using hash(fname)
    )engine=memory;

散列方法是指根据记录的查找键值，使用一个函数计算得到的函数值作为磁盘块的地址，对记录进行存储和访问。  
在数据库技术中，一般使用“桶”作为基本的存储单位，一个桶可以存放多条记录。

## 桶溢出解决方法 ##

### 溢出桶拉链法 ###

溢出的桶用指针链接在原来的桶的后面。

### 开放式散列法 ###

**线性探查法**  
在溢出桶位置的下面顺序选择一个空闲的桶。  
**再散列探查法**  
如果桶溢出，则使用第二个散列方法再选择另外一个桶位置。  
hash索引跟B树索引一个很大的区别是，hash索引只能进行确定值的搜索，而不能模糊搜索。因为hash索引搜索是通过得到关键值的hash方法值，来得到记录的地址，所以也不能通过hash索引进行排序。

## hash索引的缺点 ##

仅仅能满足“=”，“IN”，不能使用范围查询  
无法被用来避免数据的排序操作  
不能利用部分索引键查询  
不能避免表扫描  
遇到大量hash值相等的情况下性能并不比BTree高

# 位图索引 #

## 概念 ##

位图索引，是一类特殊的数据库索引技术，其索引使用bit数组（或称bitmap、bit set、bit string、bit vector）进行存储与计算操作。  
如果用户查询的列的基数非常的小， 即只有的几个固定值，如性别、婚姻状况、行政区等等。要为这些基数值比较小的列建索引，就需要建立位图索引。

## 存储空间 ##

相对于B\*Tree索引,位图索引由于只存储键值的起止Rowid和位图,占用的空间非常少.  
bitmap的空间占用主要跟以下4个因素相关:  
a.表的总记录数  
b.索引列的键值多少,列的不同值越少,所需的位图就越少.  
c.操作的类型,批量插入比单条插入所需的位图要少得多,8i,9i下是这样的,10G则没有这种区别,详见后面的分析.  
d.索引列相同键值的物理分布,8i,9i中,不同块上的数据,相同的键值,会建立不同的位图行(段)来表示

## 适用条件 ##

位图索引适合只有几个固定值的列，如性别、婚姻状况、行政区等等。  
此外，位图索引适合静态数据，而不适合索引频繁更新的列。

## 与BTree索引对比 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70]: /images/20211116/beaafe654e634779b2367f74ceafad34.png