索引概述
索引是用于MySQL高效获取数据的数据结构，用于快速查找
优点
- 提高数据检索效率，降低磁盘IO
- 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性
- 在实现数据的参考完整性方面，可以加速表和表之间的连接
- 可以减少查询中分组和排序的时间
缺点：
- 创建和维护索引需要耗费时间，且随着数据量的增加，所耗费的时间也会增加
- 索引需要占用磁盘空间
- 虽然索引提高了查询速度，但会同时降低更新表的速度。当对表进行增删改数据的时候，索引也需要动态的维护（保持数据的有序性）
如果需要频繁的更新表，最好的方法就是，先删除索引，更新完数据后，最后再创建索引。
常见索引概念
索引可以分为两种：聚簇索引和非聚簇索引（也称二级索引、辅助索引）。
聚簇索引
聚簇索引中，根据主键顺序建立索引，所有的用户记录都存储在了叶子节点中。索引即数据，数据即索引，二者合一
特点：
- 根据记录主键值的大小，进行记录和页的排序
- 一个页内的记录按照逐渐的大小顺序排成一个单向链表
- 各个存放用户记录的页顺序排成双向链表
- 存放目录项记录的页分为不同层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表
- B+树的叶子节点存储的是完整的用户记录
优点：
- 数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，比非聚簇索引查询效率更高
- 聚簇索引对于主键的排序和范围查找速度块
- 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省大量得IO操作
缺点：
- 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
- 更新主键代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新
- 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据（回表）
注意：
- InnoDB会自动的创建聚簇索引，MyISAM不支持聚簇索引
- 每个MySQL表中只有一个聚簇索引，一般为表的主键
- 如果没有定义主键，InnoDB会选择非空的唯一索引代替。如果依然没有这样的字段，InnoDB会隐式的定义一个主键来作为聚簇索引
- InnoDB表尽量使用递增有序的ID作为主键
非聚簇索引（二级索引、辅助索引）
可以以其他非主键的字段，建立非聚簇索引。在非聚簇索引中，叶子节点只记录需要建立非聚簇索引的字段值以及主键
所以在查找非聚簇索引时，需要两次查找索引。首先找到主键值，然后根据主键值在聚簇索引中找到完整的用户记录，这个过程称为回表。
联合索引：同时为多个列建立索引，本质上也是二级索引。比如按照c1列进行排序，当c1相同时，按照c2进行排序
InnoDB的B+树注意事项
根页面位置万年不动：自上而下构建B+树
内节点中目录项记录的唯一性：在二级索引中，把主键值也添加到二级索引内节点的目录项中，保证唯一性
一个页面最少存储2条记录
InnoDB和MyISAM的对比
二者区别如下：
- InnoDB中有1个聚簇索引；MyISAM的索引都是非聚簇的
- InnoDB的数据文件本身就是索引文件；而MyISAM索引文件和数据文件是分离的，索引文件中仅仅记录数据记录的地址
- InnoDB的非聚簇索引记录的是主键值；而MyISAM索引记录的是地址
- MyISAM的回表操作十分快速，因为得到的是地址（文件偏移量）；而InnoDB需要通过主键再次在聚簇索引中查找
- InnoDB要求表必须有主键。如果没有指定主键，MySQL会自动选择一个非空唯一的字段作为主键。如果依然不存在这种队列，MySQL会自动为InnoDB表生成一个隐含字段作为列，长度为6字节，类型为长整型
索引的其他结构
Hash索引
MySQL中的Memory引擎支持Hash索引
缺陷
Hash索引查找效率高，为何MySQL索引结构设计成树形结构？
- Hash索引进能够满足=、<>和IN查询，效率较高。如果进行范围查询，Hash索引的时间复杂度会退化为
O(n) - Hash索引中，数据的存储是没有顺序的，ORDER BY时需要对数据重新排序
- 对于联合索引的情况，Hash值是将联合索引键合并后计算的，无法对单独的键进行查询
- 如果Hash索引列的重复值较多，查询效率会降低
自适应Hash索引
InnoDB不支持Hash索引，但是提供自适应Hash索引。
如果某个数据经常被访问，当满足一定条件后，会将这个数据页的地址存放到Hash表中。在下次查询时，可以直接找到这个页面的位置
B树
B树是一种多路平衡搜索树
B树与B+树的主要区别：
- B树数据记录不仅在叶子节点中，也同样在分支节点中，所有节点内的数据没有冗余；B+树的数据记录仅仅存放在叶子节点中，分支节点与叶子节点有冗余数据
- B树每个节点内存放M个键值和M+1个指针；B+树的每个节点存放M个键值和M个指针
- B+树的叶子节点通过链表顺序连接起来，支持顺序查找
B+树的分支节点不直接存储数据，为什么？
- B+树查询效率更加稳定。B+树的数据记录只存在于叶子节点中
- B+树的查询效率更高。分支节点仅仅存放索引信息，不存放数据记录。与B树相比，数据页可以存放更多的关键字
- 在范围查询上，B+树的效率更高。所有数据都在叶子节点上，叶子节点用过链表相互连接并且有序，所以范围查询的效率更高