为什么MySQL索引要使用B+树

B+树的优点

1. B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快。

2. B+树查询速度更稳定：B+所有关键字数据地址都存储在叶子节点上，所以每次查找的次数都相同，所以查询速度要比B树更稳定。

3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时更方便，数据紧密型很高，缓存的命中率也会比B树高。

4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

为什么不用二叉树

二叉树最坏情况下会退化为链表，例如在原数据有序的情况下。

为什么不用红黑树

红黑树也叫二叉平衡树，红黑树可以有效解决掉顺序数据一次放入二叉树而导致的形成链表的结果，但是红黑树一个节点只能存储一个数据，就导致如果是大量的数据，红黑树的高度就不可控，如果一个红黑树是20的高度，要查询的数据在叶子结点，则表示需要需磁盘20次IO，效率还是不高。

为什么不用B树

B树比红黑树的优势是，B树是一个节点上存储多个数据，比如磁盘的一页数据，这样的横向扩展，相同的数据量就可以比红黑树减少更多的高度，从而减少了磁盘的IO次数，下面开始对比B树和B+树，就会发现B+树在查询数据方面要比B树有很多便捷的地方。

B树：data为数据的磁盘地址，还可能是整条列的数据

1. 数据是分散在每个结点上的，所有结点元素不重复。

2. 结点元素从左到右递增。

3. 叶子结点具有相同的深度，叶子结点的指针为空。

B+树：data为数据的磁盘地址，还可能是整条列的数据

1. 叶子结点包含了所有的索引字段，以及数据的磁盘地址，而非叶子结点不在存储data数据，作用只是便于查找的冗余索引。

2. 非叶子结点是从子结点选取一页的开头来作为自己的值，指针为子结点那页的地址。

3. 每一个结点里的值都是排好序的。

4. 叶子结点之间还有指针可以互相访问，这样方便了范围查找，比如where col > 10，这是mysql对B+的变种，也是对比B树的一个优势。

5. 由于data可能会很大，非叶子结点在不存储data后，非叶子可以存储的元素则会变多，还可以降低树的高度，提高了查询的效率，这是与B树对比，B+树的一个优势。

总结

数据库使用B+树肯定是为了提升查找效率。

但是具体如何提升查找效率呢？

查找数据，最简单的方式是顺序查找。但是对于几十万上百万，甚至上亿的数据库查询就很慢了。

所以要对查找的方式进行优化，熟悉的二分查找，二叉树可以把速度提升到O(log(n,2))，查询的瓶颈在于树的深度，最坏的情况要查找到二叉树的最深层，由于，每查找深一层，就要访问更深一层的索引文件。在多达数G的索引文件中，这将是很大的开销。所以，尽量把数据结构设计的更为‘矮胖’一点就可以减少访问的层数。

在众多的解决方案中，B-/B+树很好的适合。B-树定义具体可以查阅，简而言之就是中间节点可以多余两个子节点，而且中间的元素可以是一个域。

相比B-树，B+树的父节点也必须存在于子节点中，是其中最大或者最小元素，B+树的节点只存储索引key值，具体信息的地址存在于叶子节点的地址中。这就使以页为单位的索引中可以存放更多的节点。减少更多的I/O支出。

因此，B+树成为了数据库比较优秀的数据结构，MySQL中MyIsAM和InnoDB都是采用的B+树结构。不同的是前者是非聚集索引，后者主键是聚集索引，所谓聚集索引是物理地址连续存放的索引，在取区间的时候，查找速度非常快，但同样的，插入的速度也会受到影响而降低。聚集索引的物理位置使用链表来进行存储。