索引数据一般是存储在磁盘中的，但是计算数据都是要在内存中进行的，如果索引文件很大的话，并不能一次都加载进内存，所以在使用索引进行数据查找的时候是会进行多次磁盘IO，将索引数据分批的加载到内存中，因此一个好的索引的数据结构，在得到正确的结果前提下，一定是磁盘IO次数最少的。

目前MySQL其实是有两种索引数据类型可以选择的，一个是BTree（实际是B+Tree）、一个Hash。

但是为什么在实际的使用过程中，基本上大部分都是选择BTree呢？

因为如果使用Hash类型的索引，MySQL在创建索引的时候，会对索引数据进行一次Hash运算，这样根据Hash值就能快速的定位到磁盘指针了，就算数据量很大，也能快速精准的定位到数据。

B-Tree为了保证数据的平衡，会做一系列的操作，这个保持平衡的过程比较耗时间，所以在创建索引的时候，要选择合适的字段，并且不要过多的创建索引，创建索引过多的话，在更新数据的时候，更新索引的过程也比较耗时。经过上面的分析，现在我们可以总结一下MySQ选择了B+Tree作为它索引的数据结构的原因。

1.首先和平衡二叉树相比，B+Tree的深度更低，节点保存关键字更多，磁盘IO次数更少，查询计算效率更好。

2.B+Tree的全局扫描能力更强，若是想根据索引数据对数据表进行全局扫描，B-Tree会将整棵树进行扫描，然后逐层遍历。而B+Tree呢，只需要遍历叶子节点即可，因为叶子节点之间存在顺序引用的关系。

3.B+Tree的磁盘IO读写能力更强，因为B+Tree的每个分支节点上只保存了关键字，这样每次磁盘IO在读写的时候，一页16K数据量可以存储更多的关键字了，每个节点上保存的关键字也比B-Tree更多了。这样B+Tree的一次磁盘IO加载的数据比B-Tree的多很多了。

4.B+Tree数据结构中有天然的排序能力，比其他数据结构排序能力更强而且排序时，是通过分支节点来进行的，若是需要将分支节点加载到内存中排序，一次加载的数据更多。

5.B+Tree的查询效果更稳定，因为所有的查询都是需要扫描到叶子节点才将数据返回的。效果只是稳定而不一定是最优，若是直接查询B-Tree的根节点数据，那么B-Tree只需要一次磁盘IO就可以直接将数据返回，反而是效果最优。