索引，类似于图书目录，可以根据目录某个页码立即找到对应的内容。
索引的有点显而易见：（有可能）提升查询效率
同时也有缺点：增大数据库空间占用，降低表更新的效率

从实现上来说，索引可以分为两种：聚集索引、非聚集索引。
说到索引的实现，不得不提B+树，提到B+树，就要先搞明白B树。

一、B树与B+树

1.B树

B树是一种多路平衡查找树，一个高度为m的B树有以下几个特点：
1.根节点至少有两个子节点；
2.每个中间节点都包含k-1个元素和k个子节点，其中m/2 <= k <= m；
3.每个叶节点包含k-1个元素，其中m/2 <= k <= m；
4.所有的叶节点都位于同一层；
5.每个节点中的元素从小到大排列，节点中k-1个元素正好是k个子节点所包含元素的值域划分。

B树

查找

MySQL将数据按照页来存储，默认一页为16KB，查询时，不会只加载某一条数据，而是将目标所在的页都加载到PageCache中。B树中，一个节点代表了一页，查找的时候，每经过一个节点就需要一次磁盘IO，可以发现，以上图中的B树为例，查找的最坏情况需要3次磁盘IO，即树的高度。

插入

B树还有一个特点，自平衡，这也使得其在插入新数据的时候比较复杂。还是用上图的B树举例，假设我们要插入一个新值4。自顶向下查找到应该插入的位置，发现应该在3,5之间。

插入4

节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。

自平衡

删除

再来看看删除，假设我们要删除11这个数据。

删除11

删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）

左旋

最终结果

B树主要应用于文件系统及某些数据库索引，比如MongoDB。对于同等数量的数据，相较于二叉查找树，B树的每一层能存放更多数据，二叉树比较“瘦高”，而B树比较“胖矮”，这样能有效减少查询过程中磁盘IO的次数。

2.B+树

B+树在B树的基础上做了改进。先来看看B+树的特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树

图中的B+树，父节点中的元素是各子节点中的最大元素。可以发现，根节点的最大值15，也是整个树的最大值；此外，所有的叶节点包含了全量元素，每个叶节点都有一个指针指向下一个叶节点，形成了一个有序链表。

除此之外，还需要了解一个概念——卫星数据（Satellite Data）。所谓卫星数据，指的是索引元素所指向的数据记录，比如数据库中的某一行。B树中，无论是中间节点还是叶节点，都带有卫星数据。这个特点会导致中间节点不能存储大量的索引。

B树

而B+树针对这个做了优化，只有叶节点带有卫星数据，中间节点只包含索引元素和指针。

B+树

我们假设一个非页子节点是 16kb，每个索引，即主键是 bigint，即 8b，指针为 8b。那么每页能存储大约 1000 个索引(16KB / (8B + 8B))。
而一颗 3 层的 B+树能够存储多少索引呢？如下图：

索引

大约能够存储 10 亿个索引。由此可见，相比于B树，B+树更加矮胖，查询的时候（平均情况下）磁盘IO的次数更少。

除此之外，范围查询时，B树找到范围起始的索引元素后，只能通过中序遍历的方式，过程复杂；而B+树由于叶节点全量的元素形成了一个链表，方便快捷。

相比较于B树，B+树实现索引有以下三个特点：1.更少的磁盘IO；2.查询性能稳定（因为IO次数总等于树高）；3.范围查询简便。

二、索引分类

1.单列索引 与 复合索引

只包含一个字段的索引叫做单列索引，包含两个或以上字段的索引叫做复合索引（或组合索引）。建立复合索引时，字段的顺序极其重要。
下面这个SQL语句在 列X，列Y，列Z 上建立了一个复合索引。

CREATE INDEX 索引名 ON 表名(列名X, 列名Y, 列名Z);

其实这相当于建立了三个索引，分别是：
1、单列索引（列X） 2、复合索引（列X, 列Y） 3、复合索引（列X，列Y，列Z）。

2.唯一索引 与 主键

唯一索引是在表上一个或者多个字段组合建立的索引，这个（或这几个）字段的值组合起来在表中不可以重复。一张表可以建立任意多个唯一索引，但一般只建立一个。

主键是一种特殊的唯一索引，区别在于，唯一索引列允许null值，而主键列不允许为null值。一张表最多建立一个主键，也可以不建立主键。

3.聚簇索引、非聚簇索引

聚簇索引的叶子节点就是数据节点，而非聚簇索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。通常我们建表的时候，会指定一个字段为主键，主键唯一且不能为空，一般情况下主键就是聚簇索引。一张表只允许存在一个聚簇索引，因为真实数据的物理顺序只能有一种。如果一张表上还没有聚簇索引，为它新创建聚簇索引时，就需要对已有数据重新进行排序，所以对表进行修改速度较慢是聚簇索引的缺点，对于经常更新的列不宜建立聚簇索引。

我们总说的数据库调优的手段之一——建索引，通常指的是非聚簇索引。一张表可以建立任意多个索引，每个索引可以是任意多个字段的组合。索引可能会提高查询速度（如果查询时使用了索引），但一定会减慢写入速度，因为每次写入时都需要更新索引，所以索引只应该加在经常需要搜索的列上，不要加在写多读少的列上。

执行某条查询SQL，从非聚簇索引到聚簇索引，再到数据节点，流程如下：

不管以任何方式查询表， 最终都会利用主键通过聚簇索引来定位到数据， 聚簇索引（主键）是通往真实数据所在的唯一路径。然而凡事都有例外，有一种非主流的方式可以不通过聚簇索引就能查询出所需要的数据，这就是覆盖索引。当为字段建立索引以后， 字段中的内容会被同步到索引之中， 如果为一个索引指定两个字段， 那么这个两个字段的内容都会被同步至索引之中。

先看下面这个SQL语句

-- 建立索引
create index index_birthday_and_user_name on user_info(birthday, user_name);
-- 查询生日在1991年11月1日出生用户的用户名
select user_name from user_info where birthday = '1991-11-1'

这句SQL语句的执行过程如下：

通过非聚集索引index_birthday_and_user_name查找birthday等于1991-11-1的叶节点的内容，然而， 叶节点中除了有user_name表主键ID的值以外， user_name字段的值也在里面， 因此不需要通过主键ID值的查找数据行的真实所在， 直接取得叶节点中user_name的值返回即可。 通过这种覆盖索引直接查找的方式， 可以省略不使用覆盖索引查找的后面两个步骤， 大大的提高了查询性能。

4.其他

其他索引的类型还有外键索引、全文索引等，这里简单带过，不再展开来讲。

外键索引：只有InnoDB类型的表才可以使用外键索引，保证数据的一致性、完整性和实现级联操作。

全文索引：MySQL 自带的全文索引只能用于 InnoDB、MyISAM ，并且只能对英文进行全文检索，一般使用全文索引引擎（ES，Solr）。