前言

谈到索引，大家并不陌生。索引本身是一种数据结构，存在的目的主要是为了提高数据查询效率，最大程度减少磁盘 IO。那么Mysql InnoDB存储引擎为什么选择B+树，而不是二叉树、B树，Hash等数据结构呢？

使用二叉树会有哪些问题？

了解过二叉树的都知道，一个节点只能有两个子节点，一个子节点只能存储一个数据，数据量大的情况下构建的二叉树高度会很高，在查找比对时次数也随之增多，像MySQL这样使用磁盘存储的数据库来说，就不太适用了，因为每经过一个节点，实际上就需要一次磁盘IO，而我们知道磁盘IO与内存比起来是相当耗时的，如果按照这样的存储方式，可能刚存个几千条数据就查询就已经非常非常慢了。

二叉树

Hash索引会有什么问题？

Hash索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位找到数据，即等值查询效率比较高，不像B树索引需要从根节点逐层遍历IO查找，所以 Hash 索引的查询效率要远高于 B树。 但是即便是这样高效的索引结构也有它的缺陷。

• 哈希索引数据并不是按照索引值顺序存储的，所以也就无法起到排序作用；
• 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如,在数据列(A,B) 上建立哈希索引,如果查询只有数据列A,则无法使用该索引；
• 哈希索引只支持等值比较查询，不支持任何范围查询；

所以Hash索引只合适一些不需要范围查询的特殊场景。

为什么是B+树而不是B树

B树

相比前面的二叉树，B树的优势是一个节点上可以存储多个数据，比如磁盘的一页数据，这样构建的一棵树高度不会太高，从而减少了磁盘的IO次数。下面开始对比B树和B+树，就会发现B+树在查询数据方面要比B树高效的多。

• B树每个节点都存放索引信息和数据地址，B+树非叶子节点只存放索引信息，叶子节点存放所有的数据，这使得非叶子节点可以存放更多的索引信息，这样构建出来的树高不不会太高，IO次数不会太多；
• B+树所有的相邻叶子节点数据存在双向指针，范围查找时更加便捷；
• B+树查询速度更稳定：B+所有数据都存储在叶子节点上，所以每次查找的次数都相同，所以查询速度要比B树更稳定
• B+树遍历全部节点更快，由于数据全部存放在叶子节点，只需要遍历叶子节点即可，不需要像B树那样，每个节点逐层遍历；

综上所述，Mysql索引数据结构主要采用B+树，B+树其实是B树的升级版，适合组织大量数据，一颗高度为3的B+树，可以存放千万级别的数据表，提高查找效率以及查询时减少磁盘的IO操作。