MySQL有哪些索引方法？
在MySQL中，我们可以看到两种索引方式：
B-Tree索引
Hash索引
实际场景下，我们基本仅仅使用B-Tree索引
对于Hash索引，我们了解即可，面试重点是掌握B-Tree索引的原理。
什么是B-Tree索引？
B-Tree是为磁盘等外存储设备设计的一种平衡查找树。因此在讲B-Tree之前先了解一下磁盘的相关知识。
系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。
InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可以通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：
show variables like 'innodb_page_size';而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干个地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有
助于定位数据记录得位置，这将会减少磁盘I/O次数，提高查询效率。
定义：B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key， data]，key为记录得键值，对应表中的主键值，data为一行记录中出主键外的数据。对于不同的记录，key值互不相同。
一颗 m 阶的B-Tree有如下特性：
每个节点最多有m个孩子。
除了根节点和叶子结点外，其他每个节点至少有Ceil(m/2)个孩子。
若根节点不是叶子结点，则至少有2个孩子。
所有叶子结点都在同一层，且不包含其他关键字信息。
每个非叶子节点包含n个关键字信息（P0,P1,....Pn,k1,...kn）
关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
ki(i=1,...n)为关键字，且关键字升序排序。
Pi(i=0,...n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)。
B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：
B-Tree的结构
每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的key和三个指向子树根节点的point，point存储的是子节点所在磁盘块的地址。两个key划分成的三个范围域，对应三个point指向的子树的数据的范围域。
以根节点为例，key为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为[17~35]，P3指针指向的子树的数据范围为大于35，即为
0~17
17~35
>35
模拟查找key为29的过程：
根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
比较key29在区间[17, 35]，找到磁盘块1的指针P2。
根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
比较key29在区间[26, 30]，找到磁盘块3的指针P2.
根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
在磁盘块8中的key列表中找到key29。
分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的key 是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O读取到内存的数据都发挥了作用，从而提高了查询效率。
什么是B+Tree 索引？
想深入学习B+树数据结构的可以看第三讲
B+Tree是在B-Tree基础上的一种优化，使其更适合外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。
从上一个问题中的B-Tree结构图中可以看到，每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。
在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。
B+Tree相对于B-Tree有几点不同：
非叶子节点只存储键值信息。
所有叶子结点之间都有一个链指针。
数据记录都存放在叶子节点中。
将上一个问题的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：
B+Tree的结构
通常在B+Tree上有两个
头指针，一个指向根节点，另一个指向关键字的最小的叶子节点，而且所有叶子结点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找；
另一种是从根节点开始，进行随机查找。
可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里K取值为103）。也就是说一个深度为3的B+Tree索引可以维护103 * 103 * 103 = 10亿条记录。
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时最多只需要1~3次磁盘I/O操作。
B+Tree有哪些索引类型？
在B+Tree中，根据叶子节点的内容，索引类型分为主键索引和非主键索引。
主键索引的叶子节点存的数据时整行数据（即具体数据）。在InnoDB中，主键索引也被称为
聚集索引或聚簇索引（clustered index）。非主键索引的叶子节点存放的数据是郑涵数据的主键，键值是索引。在InnoDB中，非主键索引也被称为
辅助索引或二级索引（secondary index）。
二级索引的叶子节点存储的是主键值，而不是行指针，这是为了减少当出现行移动或数据页分裂时二级索引的维护工作，但会让二级索引占用更多的空间。
辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，需要通过两步：
首先，InnoDB存储引擎会遍历辅助索引找到主键。
然后，再通过主键在聚集索引中找到完整的行记录数据。
另外，InnoDB通过主键聚簇数据，如果没有定义主键，会选择一个唯一的非空索引代替，如果没有这样的索引，会隐式定义个主键作为聚簇索引。
再另外，可能有跟我一样的疑惑，在辅助索引如果相同怎么存储？最终存储到B+Tree非叶子节点中时，它们对应的主键ID是不同的，所以妥妥的。如下图所示：
相同的索引怎么存储
聚簇索引的注意点有哪些？
聚簇索引表最大限度地提高了I/O密集型应用的性能，但它也有一下几个限制：
插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键。
关于这一点，可能面试官会换一个问法。例如，为什么主键需要时自增ID，又或者为什么主键需要带有时间性关联。
更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
MySQL默认情况下，主键是允许更新的。对于MnogoDB，其主键是不允许更新的。
二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。
当然，有一种情况可以无需二次查找，基于非主键索引查询，但是查询字段只有主键ID，那么在二级索引中就可以查找到。
主键ID建议使用整型。因为，每个主键索引的B+Tree节点的键值可以存储更多主键ID，每个非主键索引的B+Tree节点的数据可以存储更多主键ID。
什么是索引的最左匹配特性
当B+Tree的数据项是复合的数据结构，比如索引(name, age, sex)的时候，B+Tree是按照从左到右的顺序来建立搜索树的。
比如当
(张三, 20, F)这样的数据来检索的时候，B+Tree会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据。但当
(20, F)这样的没有name的数据来的时候，B+Tree就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。比如当
(张三, F)这样的数据来检索时，B+Tree可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据。
这个是非常重要的性质，即索引的最左匹配特性。
MyISAM索引实现？
MyISAM索引的实现，和InnoDB索引的实现是一样使用B+Tree，差别在于MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
主键索引
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：
这里设表一共有三列，假设我们以Col1为主键，上图是一个MyISAM表的主索引（Primary Key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。
辅助索引
在MyISAM中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构图如下图所示：
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
MyISAM索引与InnoDB索引的区别？
InnoDB索引是聚簇索引，MyISAM索引是非聚簇索引。
InnoDB的主键索引的叶子节点存储着行数据，因此主键索引非常高效。
MyISAM索引的叶子节点存储的是行数据地址，需要再寻址依次才能找到数据。
InnoDB非主键索引的叶子节点存储的是主键和其他带索引的列数据，因此查询时做到覆盖索引会非常高效。
覆盖索引，指的是基于非主键索引查询，但是查询字段只有主键ID，那么在二级索引中就可以查找到。