在mysql优化中，当我们定位到了慢查询语句后，我们都会适当给它建立索引来提高查询效率。是的，索引的作用就是高效提高查询效率，这种效果是非常明显的。不过，建立索引后，也带来了一些弊端，那就是作增加、删除等更新操作时，效率会下降，因为要对这些索引文件进行维护，必然导致效率下降。
之所以加了索引后，查询效率就快了，这很大程度上取决索引背后所使用的数据结构。在查找算法中，二分查找比遍历一遍的效率高许多，而在数据结构中，二叉查找树，甚至其进化版的红黑树的查找效率也是很高的，尤其是红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（logn）。对于红黑树还不是很理解的话，可以看博主之前总结过的这篇文章。
但是，多数数据库的索引却是使用了B树，而不是红黑树这种数据结构。在MySQL中则使用了B树的优化版B+树。这些都是有原因的。
原因在于B树能够充分利用磁盘预读原理，而红黑树由于逻辑上很近的节点，物理上可能很远，无法利用局部性，导致效率比B树差很多。我们来了解一下什么是局部性原理和磁盘预读原理
局部性原理与磁盘预读：
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，
磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，
要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，
而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，
顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。我们来分析一下B树的性能效率
假设B树的高度为h,B树一次检索最多需要h - 1次I/O(因为根节点常驻在内存中)。
h =
但数据库系统巧妙利用了磁盘预读原理后，将一个节点的大小设为等于一个页。B树新建一个节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。
渐进复杂度变为O（h）=
,一般实际应用中，出度d是非常大的，通常超过100，因此h非常小（通常不超过3），三层的B树可以存放上百万数据。也就是说，最多需要2次I/O就可以查找目标数，性能可见极其强悍！
而红黑树由于逻辑上很近的节点，物理上可能很远，无法利用局部性，其渐进复杂度也为之前的O（h）。效率与B树无法比较。
这里有一篇漫画，说的是B树与B+树的一些知识点，大家可以看一下
之所以要用B+树，原因在于B+树的特性。
1.B+树的中间节点只保存索引元素，不保存数据，导致可以有更多的空间存放更多的索引，减少I/O次数。
2.B+树中间节点可以存放的元素个数为K，而B树为K - 1(K 为该节点的子树数目)，导致B+树显得更加“矮胖”，更符合做索引。
3.B+树叶子节点才存放索引文件，并且各区间叶子节点是以指针连起来，而B树是节点都可以存放索引和数据，这个优化将在范围查询时，让B+树显得很方便，只要顺着指针链，找下去就可以了，而B树要做范围查找，则要进行中序遍历，导致进行的I/O次数比B+树多。
mysql中普遍使用B+Tree做索引，但在实现上又根据聚簇索引和非聚簇索引而不同。
所谓聚簇索引，就是指主索引文件和数据文件为同一份文件，聚簇索引主要用在Innodb存储引擎中。在该索引实现方式中B+Tree的叶子节点上的data就是数据本身。
这里顺便总结一下mysql两种存储引擎特性和优缺点
MyISAM：
优点：查询数据相对较快，适合大量的select，可以全文索引，会保持表的具体行数
缺点：不支持事务，不支持外键，并发量较小，不适合大量update操作
InnoDb：
优点：支持事务，支持外键，并发量较大，适合大量更新操作
缺点：不适合大量的查询操作，查询数据相对较慢、不保存表的具体行数，需要扫描一遍表。