MySQL索引主要有两种结构：B+Tree索引和Hash索引，接下来我们会讲解到Hash表、二叉查找树、平衡二叉树、B树以及B+树。

Hash索引

顾名思义，哈希索引是通过哈希表实现的，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（HashCode)，并且Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针。

只能用于等值查询，时间复杂度为O(1)，但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

当出现Hash冲突的时候，存储引擎必须遍历整个链表中的所有行指针，逐行比较，直到找到所有的符合条件的行，若Hash冲突很多的话，其索引维护的代价很高，并且性能并不一定会比BTree索引高。

Hash索引存储的是Hash码而不是键值，所以无法用于排序。如果是需要范围查询数据的，显然这种并不适合。

二叉查找树

如果是按照7，4，9，2，5，8，11的顺序添加节点。那么树的结构图如下：

二叉树的特点：每个节点最多有2个分叉，左子树和右子树数据顺序左小右大。

二叉树的实现主要为了每次查找都可以折半而减少IO次数，但还有种情况下很容易出现树不分叉了，这时候树退化成链表了，如下图：

平衡二叉树

平衡二叉树除了具备二叉树的特点之外，最主要的特征是它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

使用平衡二叉查找树查询时间复杂度是 O(log2n)。查询id=5，只需要两次IO。

平衡二叉树存在的一些问题：

平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高

树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。

B树(B-Tree)

MySQL的数据是存储在磁盘文件中的，查询数据时需要先把磁盘中的数据加载到内存中，磁盘IO操作非常耗时，所以我们优化的重点就是尽量减少磁盘IO操作，所以，我们应当尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。

如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？

可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘IO，我们查找数据的效率将会极低！

为了解决平衡二叉树的这个弊端，B树应运而生， B树是一种多叉平衡查找树，主要的特点是：

叶子节点都在同一层，叶子节点没有指针连接

B树的节点中存储着多个元素，每个内节点有多个分叉

节点中的元素包含键值和数据，节点中的键值从大到小排列

下面用一张图对比平衡二叉树和B树：

从中我们可以看出，将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖，在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘IO的次数，从而提升查找速度。

下面以一张图讲解在B树中查找数据的情况：

相比较二叉平衡查找树，虽然比较的次数没有明显的减少，但是磁盘IO次数大大减少，B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树创建索引可以很好的提升查询的效率。但是在实际的数据库应用中仍存在一些问题无法解决。

B树中每个节点中包含key值以及data值，而每一个节点的存储空间是有限的(MySQL默认16K)，如果data中存放的数据较大时，将会导致每个节点能存储的key的数量很小，所以当数据量很多，且每行数据量很大的时候，同样会导致树的高度变得很高，增大查询时的磁盘IO次数，进而影响查询效率。

不支持范围查询的快速查找，而在实际的应用中，数据库范围查询的频率非常高，以下的一种情况是我查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。

问题总是推动改进的前提，为了解决以上问题，对B-Tree 进行改造优化，进而演变出了B+Tree。

B+树（B+Tree）

对比B树和B+树，我们发现二者主要存在以下几点不同的地方：

数据都存放在叶子节点中

非叶子节点只存储键值信息，不再存储数据

所有叶子节点之间都有一个指针，指向下一个叶子节点,而且叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表

既然B+树解决了B树的范围查询问题，那么接下来我们来看一下等值查询和范围查询。