MySQL性能优化[理论篇]-B树索引与hash索引

系列文章：

对索引的优化是数据库性能优化方面最重要的一项，也是性能提升最显著的。

如果把数据库比作一本新华字典，那索引就是字典前面的目录了。如果不使用目录，想从字典中直接找某个字的解释，难度可想而知，但是有了目录，我们可以先从目录中找到这个字对应的页码，然后再翻到相应的页码，就能找到这个字的完整解释了。索引的工作原理和字典目录基本一致。

接下来的几篇文章我会细致的分析MySQL数据库中索引的原理以及使用上的一些技巧，并通过一些查询例子来演示索引给我们带来的性能提升到底有多大。

我们先来说说MySQL数据库中支持那些索引类型。

索引分类

一般在讨论索引类型的时候，我会按照多个方面来进行分类。

1 按索引逻辑存储结构划分可以分为：

2 按索引是建立在单独的列，还是多列上。可以分为：

3 按索引的约束条件可以划分为：

这一篇文章先来讨论“B树索引和Hash索引”。

更准确的说应该是B+树，由于创建索引语句使用的关键字为BTREE，所以一般都叫做B树索引。

其实这部分内容在我前两篇文章中已经讲得很详细，如果大家对BST，红黑树，B树，B+树不了解，可以看看这两篇文章：
二叉搜索树BST,AVL,红黑树,伸展树
B树与B+树

首先为了查询速度，索引肯定要使用便于查找的数据结构。
大学里学的查找结构无非“hash”和”BST”，hash就对应着Hash索引，这个待会儿再详细介绍。
而BST中，用的最多的就是红黑树了。
那为什么数据库不使用红黑树呢。最主要的原因是为了减少随机磁盘I/O的次数。

由于数据库存储的数据量相对较大，而且数据保存时间更久，所以数据的数据绝大多数都是存储在磁盘上的。

红黑树比较适合用在内存中(所以各种编程语言都提供了红黑树给程序员用啊)。红黑树到了磁盘上速度就不行了，B树就是专门用在磁盘上的数据结构：对于相同的数据量，B树的深度更低，经过的节点更少，所以造成的随机磁盘IO次数也就更少。(文件索引数据库索引用的都是B树)

红黑树

同样的原因：为了减少磁盘IO

首先我们知道查找结构，通过比较key来找到对应的value(也就是我们要查找的数据)。B树每个数据的Key-Value都是存储在一起的(实际上value部分只是存储了数据行的引用)，每次比较key的时候都会把value也给读取出来，这就造成了不必要的磁盘IO。
另外数据库经常会出现范围查询的需求，单纯的B树进行范围查询需要回溯到父节点，这也造成了大量的I/O操作，而且这个操作相当复杂。

为了解决这些问题B树的发明者对B树进行了一些改进。

B+树是B树的变体，它的完整数据全部存储在叶子结点，非叶子节点只存储key值，这样B+树避免了不必要的磁盘I/O，由于所有的查找最终都会到叶子结点，所以也就保证了查询性能的稳定。

同时由于B+树叶子结点使用指针串联起来，这就方便了范围查询(>、<、between等)。

而且由于B+树索引本身的有序性，所以在很多情况下可以避免对数据的排序(对磁盘排序要用到文件外排序，而且数据量很大很耗时)。

B+树

总结起来，使用B+树作为数据库索引的存储结构有以下原因：

看到这感觉B+树仿佛就是为数据库索引而设计的 (⊙o⊙)。

hash在很多编程语言中都能见到，因为它查找速度非常快，理论上平均时间复杂度能达到O(1)。

hash索引

和B树索引相比，hash索引在使用上有很大的局限性：

无序性，导致无法范围查找和索引排序。
>、<、between等范围查询无法使用索引。
对完整的key计算hash，所以不支持部分匹配。
比如对多个列创建hash索引，查找时条件必须这些列精确匹配，才能使用到hash索引。都精确匹配了，更别谈什么索引覆盖。
再比如，使用like 'hash%'进行前缀匹配，也无法使用hash索引。
由于hash索引实际只保存了数据对应的行指针，所以不能避免读取数据行(说白了还是没有索引覆盖的功能)。
当产生hash碰撞(哈希值相同)的时候，数据库要遍历拉链中所有的行指针，逐个取出数据行进行比较，数据量越大，冲突越多，查找代价越高。