先介绍下红黑树、B树、B+树。
红黑树
个人认为红黑树其实蛮难的，毕竟HashMap在JDK1.8中才使用了红黑树。
红黑树的特性：
节点存在逻辑上的颜色：黑色和红色，根节点为黑色，
叶子节点为黑色的空节点，红色节点下的子节点一定为黑色节点。
从根节点到叶子节点所有的路径上存在相同数目的黑色节点。
红黑树的这些特性导致红黑树的平衡性，从根节点到叶子节点的最长路径不会超过最短路径的2倍。
当然红黑树为了维持自身的平衡性，会存在变色和旋转。
B-树
B树是利用磁盘块的特性来构建的树结构，每个磁盘块一个节点，每个节点包含很多的关键字，数的关键字增多后数的层级就会比二叉树更少，减少了查询的次数和复杂度。其次还利用了磁盘预读的特性，把每个节点作为一个页（磁盘页大小为4K），每个节点一次I/O操作就可以完全载入。
但是由于每个节点关键字还和关键字记录指针绑定到一起，导致一个节点不能够存储过多的关键字，所以B+树就出现了。
B+树
B+树每个非叶子节点存储关键字和父节点指针，关键字记录的指针存储在叶子节点，并且叶子节点有序。这样每个非叶子节点能够存储更多的关键字，树的层级也就下降了，查询数据的速率变快。
为什么要选用B+树，而不是红黑树呢？
B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。所以从Mysql（Inoodb）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系型数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。
那么Mysql如何衡量查询效率呢？–磁盘IO次数。B-树/B+树的特点就是每层节点数目非常多，层数很少，目的就是为了减少磁盘IO次数，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。另一个优点是：B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常de频繁的，而B树不支持这样的遍历操作
红黑树基本都是存储在内存中才会使用的数据结构。在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。
Mysql的聚集索引
在MySQL的Innodb存储引擎下主键索引称为聚集索引，列索引称为辅助索引，二级索引的B+树的非叶子节点存储的数据指针是聚集索引的主键。
如上图中，id主键索引的叶子节点的数据区保存的就是真实的数据，在通过索引进行检索的时候，命中叶子节点，就可以直接从叶子节点中取出行数据。主键索引的叶子节点保存的是真正的数据。而辅助索引叶子节点的数据区保存的是主键索引关键字的值。
假如要查询name=C的数据，其搜索过程如下：先在辅助索引中通过C查询最后找到主键id=9。然后在主键索引中搜索id为9的数据，最终在主键索引的叶子节点中获取到真正的数据。所以通过辅助索引进行检索，需要检索两次索引。
为什么这样设计呢？
原因就是：如果和MyISAM一样在主键索引和辅助索引的叶子节点中都存放数据行指针，一旦数据发生迁移，则需要去重新组织维护所有的索引。
我是凯腾凯，互联网浪潮下一枚苟且偷生的程序仔