1. MySQL索引与底层实现

对于数据量庞大的MySQL库表来说，若没有建立表索引，对表中数据的删改查等操作需要对全表进行扫描，其时间复杂度为O(n),效率降低。

而索引的建立可以有效降低对表元素操作的时间复杂度；

索引类似于字典中的目录，通过字典的拼音目录，我们可以快查询到需要的内容；同样的，索引是对MySQL数据表建立的目录，当对数据进行删改查操作时，通过扫描索引来快速获得目标数据所在的真实映射。

通过学习数据结构我们可以认识到，实现索引与数据间快速映射的结构有多种实现，例如哈希表、二叉搜索树以及多种二叉搜索树的变种。目前，MySQL中实现索引所采用的底层结构为B+树，那么B+树有什么特征，才能够脱颖而出被MySQL选中呢？

1.1 哈希表

哈希表（Hash table，也叫散列表），根据关键值（key-value）直接进行访问的数据结构。

它通过把key映射到表中的一个位置来访问记录，以加快查找速度。这个映射函数被叫做散列函数，存放记录的数据叫做散列表。关于哈希表的详细介绍，可移步到第3-3章5.1节。

那么用哈希表作索引的优点在于可直接按key进行查找，效率较高O(1); 但缺点也比较明显，不能进行范围查找。

1.2 AVL树

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（得名于其发明者的名字Adelson-Velskii 以及 Landis），AVL树具有二叉搜索树的性质，同时维持高度平衡，避免因某一子树的高度不平衡使得搜索效率退化为O(n)。

平衡二叉树递归定义如下：

• 1. 左右子树的高度差小于等于1
• 2. 其每一个子树均为平衡二叉树

下图为10个节点的AVL树，其节点的值为1-10：

如果现在要查找10： （1）第一次与根4相比，大于4； （2）第二次与8相比，大于8； （3）第三次与9相比，大于9； （4）第四次与10行比，等于10 比较了4次得到查找结果；AVL树的查询效率为O(lgn),其查询效率显然是低于哈希表的；

但是由于AVL树是有序的，因此其范围查找会比哈希表高效： 如果现在需要查找大于4的元素，哈希表只能通过4快速映射到对应元素，想要查询key大于4的元素，只能扫描全表；而AVL的范围查询效率十分高校，通过O(lgn)的是件复杂度查询到key=4的节点，递归取出右子树及父节点的右子树获得范围查询结果。

1.3 B树与B+树

1.3.1 B树

B树其结构与AVL树非常相似，最大区别在于B树的节点中可以包含多个元素，即平衡多路查找树结构。

B树具有以下特点：

• 1. 每个节点最多有m-1个关键字，称为m阶
• 2. 根节点最少可以只有1个关键字
• 3. 非根节点至少有m/2个关键字
• 4. 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 5. 所有叶子节点都位于同一层

• 6.每个节点都存有索引和数据，也就是对应的key和value。

为了维护上述规则，B树的生成、插入和删除算法也较为复杂，这里不对B树生成和旋转方法做介绍。

如下图所示：

其中6和8元素、9和10元素存储在了同一个B树节点中；正是因为B树的节点可以存储多个元素，B树的高度要低于AVL树。

当我们需要查找10元素时，尽管元素比较次数仍为4次，但只需要3次对索引树的磁盘或内存I/O操作。

1.3.2 B+树

B+树是对B树的变种，二者的不同点在于：

• 1. B+树区分非叶子节点和叶子节点，非叶子节点只存储key，不存储value。叶子节点同时存储key和value。在节点存储单元固定时，B+树每个非叶子节点所能保存的key数量多于B树。
• 2. B+树叶子节点保存了非叶子节点的所有key的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
• 3. B+树的所有非叶子节点都下沉成为叶子节点，每个叶子结点都存有相邻叶子结点的指针，叶子节点按照key自小而大顺序连接。

如图所示：10个元素生成B+树的结构

1.3.3 B+树的优势是什么？

实际上，索引是需要占用存储单元的，当一个表的数据行越多，对应的索引文件也就会越大；索引需要存储在磁盘中，不能够存储在内存中；所以在选择索引的数据结构时应该考虑哪种结构适合从磁盘I/O；

通过上述的分析可知，B树和B+树是多路AVL树，二者的高度一般会低于AVL树，从而查找的磁盘I/O效率会高于AVL树；

通常B+树的非叶子节点不存储数据（只存储键值），只有叶子节点才存储数据（表的行信息或者表行的地址）；而B树的非叶子节点和叶子节点都会存储数据，会导致非叶子节点中存储的索引值会少于B+树；因此B树的高度会比B+树高，平均查找的I/O效率低。另外，B+树的叶子节点有指向相邻叶子节点的指针，提高了范围查找的效率。

Mysql中MyISAM和Innodb引擎使用B+树作为索引结构，非叶子节点不存储数据，叶子节点存储数据，一个非叶子节点内能存储更过的key值，树的度变大，I/O效率增加。

2. 聚簇与非聚簇B+树索引

通过第一节我们认识到，B+树作为索引的非叶子节点不存储数据，只存储索引值，仅在叶子节点存储索引值+数据。按照B+树叶子结点存储数据的方式区分，叶子结点存储行记录的存储地址时为非聚簇索引，叶子结点存储行记录的数据时为聚簇索引。

以下表的学生信息表为例，详细的讲解聚簇和非聚簇索引的特点与区别，以学号作为主键：

2.1 MyISAM引擎中的非聚簇索引

非聚簇索引的示意图如下图所示：

MYISAM的非聚簇索引，B+树叶子结点中存放的是数据所在的地址，因此除了建立索引所需要的查找磁盘I/O外，取数据时还需要一次地址映射的磁盘I/O。此外，主键索引和辅助索引无明显区别。

2.2 InnoDB引擎中的聚簇索引

相对的是，在InnoDB引擎中B+树以聚簇索引的形式构造，主键索引的B+输叶子结点中数据区域存储的是数据行记录，辅助索引B+树叶子结点数据区域存储主键的值。

• InnoDB中的主键索引和行数据是绑定在一起的，也意味着InnoDB的一个表一定要有主键索引；如果没有手动建立主键索引，Innodb会查看有没有唯一索引，如果有则选用唯一索引作为主键索引，如果没有唯一索引，会默认建立一个隐藏的主键索引。

• 因此，Innodb的主键索引比MyISAM的主键索引查询效率要高，少了一次最后取数据的磁盘I/O。在使用Innodb引擎时，最好手动建立主键索引，尽量利用主键索引查询。

• 此外，辅助索引的叶子结点存储的是主键值，因此通过辅助索引搜索记录时，会先得到该记录对应的主键值，再搜索主键索引树从而获得相对应的行数据信息。

3.索引的选择原则

3.1 索引选择性

为了衡量索引扫描与全表扫描哪个性能更优，定义索引选择性的概念，索引选择性是：不重复的索引值和表记录数的比值，其取值范围是【0—1】。

以第二节中构建的学生信息表为例，其中有一个性别列，这个列的包含选项就两个：男/女。那么，若以性别这一列创建索引的话，假设表中有一万条记录，那么索引的选择性为万分之二，通过该索引的查询与全表扫描的效率相似，基本没有起到优化查询的意义。如果是主键索引，由于主键id是唯一的，因此主键索引的选择性为1，索引价值最大，可以直接根据索引定位到数据。

因此，索引选择性得分越高，索引的价值越大；选择性越低，说明这列索引的重复值过多。

3.2 联合索引

一般的，在where条件后用的列通常适合建立索引来增加查询效率，但索引并不是越多越好的。根据索引选择性，有时只在某一列上建立索引，可能它的选择性很低，通过该列索引并不能把查询的范围高效率的缩小。因此，建立联合索引是一个好的方式。联合索引是一个有序元组<a1, a2, …, an>，其中各个元素均为数据表的一列。

通过构建联合索引，可以极大的提高索引选择性的得分。以第二节中构建的学生信息表为例，以<name、sex、height>三列建立联合索引，同样的它们会按照B+树的规则建立索引树。

3.3 前缀索引

尽管通过联合索引能够有效提高索引选择性，但联合索引由于B+树中的key变大，同样会增大索引文件的大小和维护开销。

前缀索引，用列的部分前缀代替整个列作为索引的key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时减少索引key节点的长度。

例如，以<left(name,5)、sex、height>三列建立联合索引，其中第一列取5个长度的前缀。

注意，为了兼顾索引选择性和索引节点的长度，去前缀索引时的长度是非固定的。前缀索引不能用于ORDER BY和GROUP BY操作。

3.4 最左前缀原则

最左前缀匹配原则：在扫描联合索引树时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配。产生最左匹配原则的原因是创建联合索引的B+树时，首先会对联合索引的最左边第一个字段排序，在第一个字段的排序基础上，然后在对第二个字段、第三个字段进行排序。

例如，有如下查询语句：

• 1. select * from table_name where name='Evila' and sex='0' and height='180'; 结论：用到了联合索引，并且sql语句中索引的顺序可以不与联合索引声明的顺序一致，因为一般数据库会进行索引优化。
• 2. select * from table_name where name='Evila'; select * from table_name where name='Evila' and sex='0'; select * from table_name where name='Evila' and sex='0' and height='180'; 结论：从最左边开始连续匹配，用到了索引

• 3.select * from table_name where sex='0'; select * from table_name where height='180'; select * from table_name where sex='0' and height='180'; 结论：不符合最左匹配原则，查询没有用到索引，而是全表扫描。

• 4. select * from table_name where name='Evila' and height='180'; 结论：用到了name列的索引，但没有用到sex列的索引，因此height列的索引也没有用到

组合索引（姓名、性别、身高）等效于（姓名、性别、身高）、（姓名、性别）以及（姓名）三个索引。基于最左前缀原则，应尽量避免创建重复的索引，例如，创建了（姓名、性别、身高）索引后，就无需再建立姓名子段的单独索引。

3.5 Explain执行计划

Explain + 一个sql语句可以返回一个表，告知此sql语句数据读取操作的类型，哪些索引可以使用，哪些索引实际使用了，表之间的引用，每张表有多少行被优化器查询等信息。在 select 语句之前增加 explain 关键字，MySQL 会在查询上设置一个标记，执行查询时，会返回执行计划的信息，而不是执行这条SQL（如果 from 中包含子查询，仍会执行该子查询，将结果放入临时表中）。

explain返回的信息如下：

mysql> explain select ... from ...;

+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+

| id | select_type | table | parti