Hash结构

根据Hash函数的运算，只需经过一次定位，便能找到需要查询数据所在的桶，不像B+树索引，要从根节点到非叶子节点，再到叶子节点，最后才能访问到我们的数据，这样可能会经过多次的IO访问，所以Hash索引的查询效率理论上要高于B+树索引。

如上这张图，比如说我们要查找Sandra Dee这么一个人，那么根据Hash函数对Key，即Sandra Dee的运算，只需一次，我们便能定位到152号桶，就是这个buckets，之后便将152号的entries全部加载到内存当中，但由于该entries是一个链表，我们顺着John Smith的指针，最终定位到Sandra Dee。

疑问

可能有些人就有疑问了，既然Hash索引的查询效率要比B+树高，为什么我们不用Hash索引作为主流索引呢？任何事务都是有两面性的，Hash索引也一样，虽然Hash索引查询效率高，但是Hash索引本身由于其特殊性也带来了很多限制和弊端。

Hash索引的缺点：

1，仅仅能满足“=”，“IN”，不能使用范围查询。

由于Hash索引比较的是进行Hash运算之后的Hash值，所以呢它只能用于等值的过滤，不能用于基于范围的查询，因为经过相应的Hash算法处理之后的Hash值的大小关系并不能保证和Hash运算前的完全一样，如上图，我们的Sandra Dee和John Smith就取了相同的Hash值了。

2，无法被用来避免数据的排序操作。

由于Hash索引中存放的是经过Hash运算之后的值，而且Hash值的大小关系并不一定和Hash运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算。

3，不能利用部分索引键查询。

对于组合索引，Hash索引在计算Hash值的时候，是组合键，就是将组合索引键合并之后再一起进行运算的Hash的值，而不是单独计算Hash值的。所以呢通过组合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用，而B+树是支持利用组合索引中的部分索引的。

4，不能避免表扫描。

Hash索引是将索引键通过Hash运算之后，将运算结果的Hash值和所对应的行指针信息存放在一个bucket当中的，由于不同索引键存在相同的Hash值，所以即使取出满足某个Hash键值的那些数据，也无法从Hash索引中直接完成查询，还是要通过访问bucket中的实际数据进行相应的比较，这就是不能避免表扫描的原因。

5，遇到大量Hash值相等的情况后性能并不一定就会比B树索引高。

对于选择性比较低的索引键，如果创建Hash索引，那么将会存在大量记录指针信息存放于同一个bucket的情况，从而造成整体性能非常低下。就跟我们前面用到的二叉树一样，有可能会变成线性的存储结构，有可能在一种很极端的情况下，所有的键计算出来的Hash值都是一样的，也就是都放在同一个bucket中，那我们查询bucket的最后一条数据的时候，就会变成线性的了，所以这也是Hash索引不能成为主流索引的原因，因为它比较的不稳定。

BitMap——位图索引

当表中的某个字段只有几种值得时候，就比如我们要表示性别的时候，只有男女两种情况，如果仅仅是为了在这个字段上实现高效的统计，此时用位图索引是一个最佳选择了。不过很少有数据库支持位图索引，比较主流的是Oracle。

位图索引的结构类似于B+树，B+树用来定位叶子节点，这些节点包含指定键值的位图段，位图段就位于叶子节点上，它的段信息就是下面的那些数字。

由于数据的值总类固定，像这里只有Blue，Green，Red，Yellow四种，所以在存储方式上，会先按照状态值进行分开，然后每一种值的空间会存储每个实际的数据行是否是这个值，我们可以看到这里有0101这样的位图，比如第一行是Blue，我们就用1来表示，第二行不是就用0来表示。在这种情况下，由于只需要存储“是”与“否”，所以通常只需要一个bit位来存放，因此理论上一个叶子块，可以存放非常多的bit位，来表示不同的行，因此用它来统计时是非常快的，加载到内存中之后，几乎是存cpu的叠加操作。

那位图索引固然好，但是它只适用于某个字段的值只有固定的几种情况，同时需要注意的是，位图索引有一个很大的缺陷，就是它的锁的力度非常大。当尝试新增或修改一条数据的时候，通常与它在同一个位图的数据操作都会被锁住，因为某行所在的位置顺序有可能会因为数据的添加或删除而发生改变，所以它并不适合高并发的联机事务处理系统，即咱们常见的OLTP系统，而适合于并发较少，而统计运算较多的OLAP（联机分析处理）类系统。