目录
一、介绍
1.1 优点
1.2 缺点
二、InnoDB中的索引数据结构
2.1 没有索引
2.2 建立索引
2.3 索引分类
2.3.1 聚簇索引
2.3.2 二级索引
2.3.3 联合索引
三、MyISAM的索引
3.1 MyISAM 与 InnoDB对比
四、索引的代价
4.1 空间上的代价
4.2 时间上的代价
一、介绍
索引（Index）是帮助MySQL高效获取数据的数据结构。
1.1 优点
（1）类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的IO成本 ，这也是创建索引最主要的原因。
（2）通过创建唯一索引，可以保证数据库表中每一行数据的唯一性 。
（3）在实现数据的参考完整性方面，可以 加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时， 可以提高查询速度。
（4）在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间 ，降低了CPU的消耗。
1.2 缺点
（1）创建索引和维护索引要耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。 （2）索引需要占磁盘空间 ，除了数据表占数据空间之 外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。 （3）虽然索引大大提高了查询速度，同时却会降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
二、InnoDB中的索引数据结构
2.1 没有索引
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能 从第一个页 沿着 双向链表 一直往下找。
2.2 建立索引
一个表中假如我们设置了这三个字段c1，c2，c3，c1为主键。
-> c1 INT, -> c2 INT, -> c3 CHAr(1), -> PRIMARY KEY(c1)
该表使用 Compact 行格式来实际存储记录，下面是简化的行格式存储示意图：
record_type={0，1，2，3}，分别标识是普通用户记录/目录项记录/最小记录/最大记录。
也可以这样看：
把若干记录放进页中就是下面的样子：
为了能快速查找到记录，我们在建索引的时候要按一个键值对记录排序 ，保证记录是有序的，通常按主键排序。这些记录用单链表连接。
然而，一个页也是有固定大小的，如果有很多条记录，那我们就要用多个页存储它们。每个页有单独的页码，页与页之间用双向链表连接。
当页足够多了，我们就要给每个页建目录记录，这样才能快速找到记录。一个目录由它所指定页上的最小主键和页码构成。这几个目录其实就是初步的索引。
等到这些目录数量足够多了，我们就把它们按主键顺序放进一个页中。
用户记录存放的有数据，而目录项记录只存放主键和页码。
同样的，一个目录页不够，我们就创建多个，目录页之间也是用双向链表连接。
在多个目录页的基础上再创建一个记录目录页的目录页 。
我们查找记录的时候从上往下，根据主键的大小，利用二分查找逐层查找页码，直到到达最下面的记录页，就能找到想要的记录。
最底层的页包含所有数据，称之为记录页；
上面几层的页只记录主键和下层的页码，称为目录页。
也就是说，B+树的 叶子节点 存储的是完整的用户记录。
这样的数据结构就叫B+树，实际上的B+树是从上往下构建的！！一般不会超过4层，因为4层所能存的数据量已经非常庞大，而层数过高反而会增加IO次数。假如有3层，那我们任何查询都只需3次IO操作来与硬盘交互。
2.3 索引分类
分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。
索引是由上往下创建的，根页面永远不变！！！！一个页至少存两条记录。
2.3.1 聚簇索引
使用记录主键值的大小进行记录和页的排序。
聚簇索引只有1个，而且如果没有设置主键的话系统会隐式地自动设置一个非空唯一主键。
优点：
1.速度快，索引和数据都在一个B+树中。
2.对于主键的 排序查找 和 范围查找 速度非常快。
3.按照聚簇索引排列顺序，查询显示一定范围数据的时候，不用从多个数据块中提取数据，节省了IO操作。
缺点：
1.插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。对于InnoDB表，我们一般都会定义一个自增的ID列为主键
2.更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
3.二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据
2.3.2 二级索引
二级索引是用字段代替 聚簇索引 中的主键的位置。 也就是按字段排序。
叶子节点存储的是单个字段和主键。
目录页增加了主键，防止出现字段相同从而无从插入新纪录的问题，下面的图不严谨。
二级索引可以有多个。使用二级索引查找时要用到两颗B+树，先找到我们要的记录对应的主键，然后根据这个主键再去聚簇索引中再查一遍。这个过程叫回表。
为什么不把所有键值都放进叶子节点？这样一次查询不就出结果了？因为太占资源了。
2.3.3 联合索引
我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引。先按一个字段排序，然后在它的基础上对另一个字段排序。
要注意联合索引与普通二级索引的区别。联合索引创建的是一个索引，将两个字段”合体“了。
三、MyISAM的索引
与InnoDB不同，MyISAM引擎使用 B+Tree 作为索引结构，叶子节点的data域存放的是数据记录的地址 。
如果我们在Col2上建立一个二级索引，则此索引的结构如下图所示：
3.1 MyISAM 与 InnoDB对比
MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：
① 在InnoDB存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，而在 MyISAM 中却需要进行一次 回表 操作（不仅要根据B+树找地址，还要再根据地址取数据），意味着MyISAM中建立的索引相当于全部都是 二级索引 。
② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是 分离的 ，索引文件仅保存数据记录的地址。
③ InnoDB的非聚簇索引data域存储相应记录 主键值 ，而MyISAM索引记录的是 地址 。换句话说， InnoDB的所有非聚簇索引都引用主键作为data域。
④ MyISAM的回表操作是十分快速 的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通 过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
⑤ InnoDB要求表 必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个 可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐 含字段作为主键，这个字段长度为6个字节，类型为长整型。
四、索引的代价
4.1 空间上的代价
每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会 占用 16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。
4.2 时间上的代价
每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。而且我们讲过，B+树每层节点都是按照索引列的值从小到大的顺序排序 而组成了 双向链表 。不论是叶子节点中的记录，还 是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序 而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需 要额外的时间进行一些 记录移位、 页面分裂 、 页面回收 等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。
