先介绍下红黑树、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一样在主键索引和辅助索引的叶子节点中都存放数据行指针，一旦数据发生迁移，则需要去重新组织维护所有的索引。我是凯腾凯，互联网浪潮下一枚苟且偷生的程序仔
转载请注明：http://www.aierlanlan.com/grrz/8322.html
