前言

数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘块（对应索引树的节点），索引树越低，越“矮胖”，磁盘IO次数就少。

两种索引结构

MySQL支持两种索引，一种是B-树索引，一种是哈希索引，大家知道，B-树和哈希表在数据查询时的效率是非常高的。

这里我们主要讨论一下MySQL InnoDB存储引擎，基于B-树（但实际上MySQL采用的是B+树结构）的索引结构。
B-树是一种m阶平衡树，叶子节点都在同一层，由于每一个节点存储的数据量比较大，索引整个B-树的层数是非常低的，基本上不超过三层。
由于磁盘的读取也是按block块操作的（内存是按page页面操作的），因此B-树的节点大小一般设置为和磁盘块大小一致，这样一个B-树节点，就可以通过一次磁盘I/O把一个磁盘块的数据全部存储下来，所以当使用B-树存储索引的时候，磁盘I/O的操作次数是最少的（MySQL的读写效率，主要集中在磁盘I/O上）。

B-树

如图：

1. 索引和数据分散在不同的节点上，离根节点近，搜索就快；离根节点远搜索就慢，花费的磁盘I/O次数不平均，每一行数据搜索花费得到时间也不平均。

2. 每一个非叶子节点上，不仅仅要存储索引（key)，还要存储索引值所在的那一行的数据。一个节点所能存放的索引key值得个数，比只存储key值得节点的个数要少的多。

3. 这棵树不方便做范围搜索，整表遍历看起来也不方便。

B+树

如图：

1. 每个非叶子节点只存放key，不存放data。好处就是每个节点存放的key更多，B+树理论上来说，层数会更低一些，搜索的效率会更好一些。
2. 叶子节点上存储了所有索引值对应的数据data：那么搜索每一个索引对应的数据，都需要跑到叶子节点上，这样每一行记录的搜索时间非常平均。
3. 叶子节点被串在一个链表上，有序链表，如果要进行索引树的搜索 & 整表搜索，或做范围查询时，直接遍历叶子节点的链表即可。

不同之处

面试题：

那么MySQL最终为什么要采用B+树存储索引结构呢，那么看看B-树和B+树在存储结构上有什么不同？

1. B-树的每一个节点，存了关键字和对应的数据地址，而B+树的非叶子节点只存关键字，不存数据地址。因此B+树的每一个非叶子节点存储的关键字是远远多于B-树的，B+树的叶子节点存放关键字和数据，因此，从树的高度上来说，B+树的高度要小于B-树，使用的磁盘I/O次数少，因此查询会更快一些。
2. B-树由于每个节点都存储关键字和数据，因此离根节点进的数据，查询的就快，离根节点远的数
   据，查询的就慢；B+树所有的数据都存在叶子节点上，因此在B+树上搜索关键字，找到对应数据的时间是比较平均的，没有快慢之分。
3. 在B-树上如果做区间查找，遍历的节点是非常多的；B+树所有叶子节点被连接成了有序链表结
   构，因此做整表遍历和区间查找是非常容易的。

哈希索引当然是由哈希表实现的，哈希表对数据并不排序，因此不适合做区间查找，效率非常低，需要搜索整个哈希表结构。