前言
MyISAM和InnoDB是MySQL最常用的两个存储引擎，本文将进行详尽的介绍和对比。对于MySQL其余几种存储引擎，请读者自行搜索学习。
本文会图解两种引擎的索引结构区别，然后讲解索引的原理，理解本文内容，就能够理解索引优化的各种原则的背后原因。
限于篇幅，本篇没有介绍的知识，会在后续博客将逐一讲解。例如：MySQL引擎的锁机制、多列索引的生效规则、索引优化等主题。
下面SQL在本篇介绍引擎的结构区别时使用的表结构，便于读者更好理解。
CREATE TABLE `user` (
`id` int(11) NOT NULL AUTO_INCREMENT COMMENT '唯一码',
`age` int(5) NOT NULL COMMENT '年龄',
`name` varchar(5) NOT NULL COMMENT '名字',
PRIMARY KEY (`id`),
KEY `name` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=92 DEFAULT CHARSET=utf8mb4;
B-树、B树和B-tree是同一个数据结构，只不过英语翻译过来之后，有些人误解了以为是多种树。所以好多讲解树的数据结构的博客完全是误导初学者。。。请读者认真分辨。
MyISAM和InnoDB的索引均采用B+树数据结构，所以接下来先介绍一下B树与B+树。
B树与B+树
B树
B树是一种多路搜索树。
- 定义任意非叶子结点最多只有M个儿子，且M>2。
- 根结点的儿子数为[2, M]。
- 除根结点以外的非叶子结点的儿子数为[M/2, M]。
- 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）。
- 非叶子结点的关键字个数=指向儿子的指针个数-1。
- 非叶子结点的关键字：K[1], K[2], …, K[M-1]，且K[i] <= K[i+1]。
- 非叶子结点的指针：P[1], P[2], …,P[M]（其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树）。
- 所有叶子结点位于同一层。
下图是一个M=4阶的B树。
B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的是叶子结点。
查找文件29的过程：
- 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。（磁盘IO操作1次）
- 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。
- 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。（磁盘IO操作2次）
- 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。
- 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。（磁盘IO操作3次）
- 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。
下面的动画是4阶B树插入的过程。
B树的特性：
- 关键字分布在整颗树的所有节点。
- 任何一个关键字出现且只出现在一个结点中。
- 搜索有可能在非叶子结点结束。
- 其搜索性能等价于在关键字全集内做一次二分查找。
B+树
下图是一个M=3阶的B+树。
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
B+树是B树的一种变形树，总结起来，数据库索引的B+树与B树的差异在于：
- 非叶子结点的子树指针与关键字个数相同。
- 非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树（注意，区间是前闭后开）。
- 为所有叶子结点增加一个链指针。
- 所有关键字都在叶子结点出现。
B+树的特性：
- 所有关键字都出现在叶子结点的链表中，且链表中的关键字是有序的。
- 搜索只在叶子结点命中。
- 非叶子结点相当于是叶子结点的索引，叶子结点是存储关键字数据的数据层。
B-/+树做索引的原因
解释这个问题之前，需要了解一些基础知识。
局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用——程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
B-/+树做索引的原因分析
一般来说，磁盘I/O次数可以用于评价索引结构的优劣。在B-Tree中查找，可知检索一次最多需要访问h个节点（上文举例查找文件29的过程）。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。
为了达到这个目的，在实际实现中，B树还使用如下技巧：
- 每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。
- B树中一次检索最多需要h-1次I/O（根节点常驻内存）。一般实际应用中，出度d（树的分叉数）是非常大的数字，通常超过100；h非常小，通常不超过3。
综上所述，用B树作为索引结构效率是非常高的。
红黑树或者平衡二叉树的其他树结构，
- h明显要深的多，执行效率低。
- 逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，
- 每个节点存储的数据量太小了，对磁盘空间造成浪费，带来频繁的IO操作。
所以其他树结构的效率明显比B树差很多。
相对B树，B+树做索引的优势
- B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
- B+树的查询效率更加稳定：由于所有数据都存于叶子节点。所有关键字查询的路径长度相同，每一个数据的查询效率相当。
- B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。
笔者认为第三条原因才是MySQL使用B+树而不是B树做索引的主要原因，毕竟MongoDB的索引是B树，所以两种数据结构并没有绝对的好坏，要看实际的业务需求。
MyISAM
磁盘存储
MyISAM在磁盘存储上有三个文件，每个文件名以表名开头，扩展名指出文件类型。
- .frm：用于存储表的定义。
- .MYD：用于存放数据。
- .MYI：用于存放表索引。
索引
主键索引
MyISAM引擎使用B+树作为索引结果，叶节点的data域存放的是数据记录的地址。
MyISAM索引文件和数据文件是分离的，索引文件仅保存记录所在页的指针（物理位置），通过这些地址来读取页，进而读取被索引的行。
树中叶子保存的是对应行的物理位置。通过该值，存储引擎能顺利地进行回表查询，得到一行完整记录。同时，每个叶子页也保存了指向下一个叶子页的指针。从而方便叶子节点的范围遍历。
辅助索引
在MyISAM中，主键索引和辅助索引在结构上没有任何区别，只是主键索引要求key是唯一的，而辅助索引的key可以重复。
Innodb
MySQL5.5开始支持InnoDB引擎，并将其作为默认数据库引擎。
磁盘存储
Innodb有两种存储方式，共享表空间存储和多表空间存储。
Innodb只有表结构文件和数据文件。
表结构文件和MyISAM一样，以表名开头，扩展名是.frm。
数据文件与存储方式有关：
- 如果使用共享表空间，那么所有表的数据文件和索引文件都保存在一个表空间里，一个表空间可以有多个文件，通过innodb_data_file_path和innodb_data_home_dir参数设置共享表空间的位置和名字，一般共享表空间的名字叫ibdata1-n。
- 如果使用多表空间，那么每个表都有一个表空间文件用于存储每个表的数据和索引，文件名以表名开头，以.ibd为扩展名。
索引
主键索引
Innodb主键索引中，既存储了主键值，又存储了行数据。
辅助索引
对于辅助索引，InnoDB采用的方式是在叶子页中保存主键值，通过这个主键值来回表（上图）查询到一条完整记录，因此按辅助索引检索实际上进行了二次查询，效率肯定是没有按照主键检索高的。
Innodb与MyISAM的区别
1. 存储结构
MyISAM存储表分为三个文件frm（表结构）、MYD（表数据）、MYI（表索引），而Innodb如上文所说，根据存储方式不同，存储结构不同。
2. 事务支持
MyISAM不支持事务，而Innodb支持事务，具有事务、回滚和恢复的事务安全。
3. 外键和主键
MyISAM不支持外键，而Innodb支持外键。MyISAM允许没有主键，但是Innodb必须有主键，若未指定主键，会自动生成长度为6字节的主键。
4. 锁
MyISAM只支持表级锁，而Innodb支持行级锁，具有比较好的并发性能，但是行级锁只有在where子句是对主键筛选才生效，非主键where会锁全表
5. 索引
MyISAM使用B+树作为索引结构，叶节点保存的是存储数据的地址，主键索引key值唯一，辅助索引key可以重复，二者在结构上相同。Innodb也是用B+树作为索引结构，数据表本身就是按照b+树组织，叶节点key值为数据记录的主键，data域为完整的数据记录，辅助索引data域保存的是数据记录的主键。
FAQ
MongoDB的索引为什么选择B树，而Mysql的索引是B+树
MongoDB不是传统的关系性数据库，而是以Json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，所以范围查询和遍历查询的需求就没那么强烈了，其次Mysql由于使用B+树，数据都在叶节点上，每次查询都需要访问到叶节点，而MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问。
总体来说，Mysql选用B+树和MongoDB选用B-树还是以自己的需求来选择的。
索引有关的名词解释
普通索引
用表中的普通列构建的索引，没有任何限制
唯一索引
唯一索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。
主键索引
根据主键建立索引，不允许重复，不允许空值；
全文索引
仅可用于MyISAM表，针对较大的数据，生成全文索引非常的消耗时间和空间（在生成FULLTEXT索引时，会为文本生成一份单词的清单，在索引时及根据这个单词的清单来索引）。
组合索引
又叫联合索引。用多个列组合构建的索引，这多个列中的值不允许有空值。可以在创建表的时候指定，也可以修改表结构。
ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')；
为了更多的提高mysql效率可建立组合索引，遵循”最左前缀“原则。创建复合索引时应该将最常用（频率）作限制条件的列放在最左边，依次递减。示例的组合索引相当于建立了col1,col1col2,col1col2col3三个索引，而col2或者col3是不能使用索引的。
最左前缀规则
假设联合索引由列(a,b,c)组成，则一下顺序满足最左前缀规则：a、ab、abc；selece、where、order by 、group by都可以匹配最左前缀。其它情况都不满足最左前缀规则就不会用到联合索引。
聚集索引
定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。
如果定义了主键，Innodb会选择主键作为聚集索引；如果没有定义主键，Innodb会选择不包含NULL值的唯一索引作为聚集索引；如果也没有这样的唯一索引列，Innodb会选择内置6字节长的rowID作为隐含的聚集索引，这里的RowId会随着记录的写入而主键自增，但是它是不可引用和查看的，是数据库引擎内部的使用。
如果我们使用自增主键，那么每次插入的新纪录都在原先记录的尾部按照顺序，添加到当前节点的索引后面，当一页快写满的时候，就会开辟一个新的页。数据记录本身就存与主索引的叶子节点上，B+tree的树。这就要求每一个叶子节点内的各条数据记录按主键顺序存放，因此每当有一条新的记录插入的时候，MYSQL会根据其主键将其插入到合适的节点和位置上，如果页面达到装载因子（INNODB默认为15/16），则开辟新的页面（节点）
如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
非聚集索引
定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。
除了InnoDB的主键索引，在mysql中的其他索引形式都是非聚集索引。
覆盖索引
指从辅助索引中就能获取到需要的记录，而不需要查找主键索引中的记录。使用覆盖索引的一个好处是因为辅助索引不包括一条记录的整行信息，所以数据量较聚集索引要少，可以减少大量io操作。
覆盖查询失效
- select选择的字段中含有不在索引中的字段 ，即索引没有覆盖全部的列。
- where条件中不能含有对索引进行like的操作。
