MySQL 索引
一、索引定义
1、为什么会出现索引？
（不考虑硬件、磁盘空间问题）
系统使用时间长之后，数据增长了，系统出现性能下降，如SQL变慢，执行时间变长、等待时间变长，也可能是SQL语句问题，索引失效现象，关联查询join过多等，服务器缓存、线程、连接池等参数设置不合理……
2、什么是索引
MySQL官方定义：索引是帮助MySQL高效获取数据的数据结构。
可以出，索引其实是一种数据结构。
索引的高效在于，索引字段按照某种数据结构完成了排序，并且在数据结构中以某种方式引用了真实的数据。
数据本身之外，数据库还维护者一个满足特定查找算法的数据结构，这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高级查找算法，这种数据结构就是索引。
一般说的索引指的是B-Tree （Balance Tree ）结构组织的索引。B-Tree 是一种多路搜索树，不一定是二叉。
其中聚集索引、复合索引、前缀索引、唯一索引默认使用B+Ttree索引，统称索引。
MySQL的索引是由存储引擎来实现的。
二、索引特点
索引基本特点：
- 索引是一种数据结构。
- 索引是自动排好序的。
- 索引需要持久化。
- 索引是存储引擎的。
1、索引持久化
索引本身也是一种数据存储表，也需要持久化，因此索引会以索引文件的形式在磁盘上存储。
如果不存储，每次启动Mysql就要重新创建。
2、索引利弊
2.1 索引优点
（1）可以提高数据检索效率，降低数据库的IO成本。
（2）通过索引列队数据进行排序，降低数据排序成本，降低CPU消耗。
2.2 索引缺点
（1）索引是一张特殊表，保存主键和索引字段，并指向实体表的记录，所以索引列也要占用空间。
（2）索引在提高检索速度的同时，降低其他操作（INSERT/UPDATE）效率。更新表时，数据保存之后还要更新索引文件。
（3）索引只是提高效率的一个因素，优秀的索引建立需要时间成本和人力成本。
3、索引分类
3.1 单值索引
一个索引只包含单个列。一个表可以有多个单例索引，一般在5个以内。
3.2 唯一索引
索引列的值必须唯一，但允许有空值。
主键索引： 索引列的值必须唯一，且不允许有空值。主键索引是特殊的唯一索引。
3.3 复合索引
一个索引包含了多个列，适用于组合搜索。效率优于索引合并。（索引合并是使用多个单列索引组合搜索）
也有称为组合索引。
3.4 全文索引
对文本的内容进行分词搜索。
三、基本语法
1、创建索引
（1）CREATE
CREATE [UNIQUE] INDEX index_name ON table_Name(colum_Name(len));（2）ALTER
ALTER table_name ADD [UNIQUE] INDEX [index_name] ON table_Name(colum_Name(len));2、删除索引
DELETE INDEX [index_name] ON table_name;3、查看索引
SHOW INDEX FROM table_name\G ;4、ALTER 加索引
（1）添加主键索引
-- 添加主键，索引列的值必须唯一，且不为NULL。
ALTER TABLE table_name ADD PRIMARY KEY (ID);（2）添加唯一索引
-- 创建索引的值必须唯一（除了NULL之外，NULL可能会出现多此）
ALTER TABLE table_name ADD UNIQUE index_name(column_name);（3）添加普通索引：
-- 添加普通的索引,单列或多列，索引列的值可能出现多此
ALTER TABLE table_name ADD INDEX index_name(column_list);（4）全文索引
-- 添加全文索引
ALTER TABLE table_name ADD FULLTEXT index_name(column_list);四、MySQL 索引结构
1、主要索引结构
MySQL索引结构主要有：
- BTree 索引
- Hash索引
- FullText 全文索引
- R-Tree 索引
- B+Tree索引（InnoDB）
2、基本原理
2.1 B-Tree 原理
B-Tree ：B-Tree是为磁盘等外存储设备设计的一种平衡查找树。
系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。
InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。
InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：
mysql> show variables like 'innodb_page_size';系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。
一棵M阶的B-Tree有如下特性：
（1）每个节点最多有M个孩子。
（2）除了根节点和叶子节点外，其它每个节点至少有Ceil(M/2)个孩子。
（3）若根节点不是叶子节点，则至少有2个孩子
（4） 所有叶子节点都在同一层，且不包含其它关键字信息
（5）每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
（6）关键字的个数n满足：ceil(M/2)-1 <= n <= M-1
（7）ki(i=1,…n)为关键字，且关键字升序排序。
（8）Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)
B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree
每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。
模拟查找关键字75的过程：
- 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
- 比较关键字75在区间（17,35），找到磁盘块1的指针P3。
- 根据P3指针找到磁盘块4，读入内存。【磁盘I/O操作第2次】
- 比较关键字75在区间（65,87），找到磁盘块3的指针P2。
- 根据P2指针找到磁盘块10，读入内存。【磁盘I/O操作第3次】
- 在磁盘块10中的关键字列表中找到关键字75。
分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。
2.2 B+Tree 原理
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有几点不同：
（1）非叶子节点只存储键值信息。
（2）所有叶子节点之间都有一个链指针。
（3）数据记录都存放在叶子节点中。
将B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：
通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。
可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1 ~ 3次磁盘I/O操作。
数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。
上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。
辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。
2.3 B+Tree演化学习
（1）二叉查找树
二叉树基本特点：左子树的键值小于根的键值，右子树的键值大于根的键值。
对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次
二叉查找树可以任意地构造，同样是2,3,5,6,7,8这六个数字，也可以按照下图的方式来构造：
但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树。
（2）平衡二叉树（AVL Tree）
平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差<=1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1；
如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下：
这四种失去平衡的姿态都有各自的定义：
LL：LeftLeft，也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。
RR：RightRight，也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。
LR：LeftRight，也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。
RL：RightLeft，也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。
AVL树失去平衡之后，可以通过旋转使其恢复平衡。下面分别介绍四种失去平衡的情况下对应的旋转方法。
LL的旋转。LL失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡。步骤如下：
- 将根节点的左孩子作为新根节点。
- 将新根节点的右孩子作为原根节点的左孩子。
- 将原根节点作为新根节点的右孩子。
LL旋转示意图如下：
RR的旋转：RR失去平衡的情况下，旋转方法与LL旋转对称，步骤如下：
- 将根节点的右孩子作为新根节点。
- 将新根节点的左孩子作为原根节点的右孩子。
- 将原根节点作为新根节点的左孩子。
RR旋转示意图如下：
LR的旋转：LR失去平衡的情况下，需要进行两次旋转，步骤如下：
- 围绕根节点的左孩子进行RR旋转。
- 围绕根节点进行LL旋转。
LR的旋转示意图如下
RL的旋转：RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转对称，步骤如下：
- 围绕根节点的右孩子进行LL旋转。
- 围绕根节点进行RR旋转。
RL的旋转示意图如下
五、应用场景
1、适宜适宜索引场景
（1）设置主键自动建立唯一索引。
（2）频繁作为查询条件的字段应该创建索引。
（3）查询中与其他表关联的字段，存在外键关系适宜建立索引。
（4）单列索/引组合索引选择，大部分不会只有一个列查询条件。
（5）查询中排序的字段，排序字段若通过索引访问可以提供排序效率。
（6）查询中要进行聚合或分组字段。
2、不适合索引的场景
（1）表记录太少不适合建索引
（2）增删改频繁的字段，创建索引会提供查询速度，但是会降低更新表速度，如INSERT/UPDATE，除了保存更新数据还要保存更新索引文件。
（3）数据重复且分布平均的字段不适合创建索引。数据列的内容重复，索引没有实际效果。
3、建索引参考值
一个列是否需要创建索引，有一个索引的选择性参考指标。
索引选择性是指索引列中不同值的数据与表中记录数的比。如果一个表中有4000条记录，表索引列有3000条不同的值，那么这个索引的选择性就是 3600/4000 = 0.90，一个索引的选择性越接近1，这个索引的效率越高。
六、聚簇索引和非聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。具体细节依赖于其实现方式。
MySQL数据库中innodb存储引擎，B+树索引可以分为聚簇索引（也称聚集索引，clustered index）和辅助索引（有时也称非聚簇索引或二级索引，secondary index，non-clustered index）。
这两种索引内部都是B+树，聚集索引的叶子节点存放着一整行的数据。
Innodb中的主键索引是一种聚簇索引，非聚簇索引都是辅助索引，像复合索引、前缀索引、唯一索引。
Innodb使用的是聚簇索引，MyISam使用的是非聚簇索引
1、聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。
聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引。
Innodb通过主键聚集数据，如果没有定义主键，innodb会选择非空的唯一索引代替。如果没有这样的索引，innodb会隐式的定义一个主键来作为聚簇索引。
优点：
（1）数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快。
（2）聚簇索引对于主键的排序查找和范围查找速度非常快
缺点：
（1）插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
（2）更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
（3）非聚簇索引（二级索引）访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据相当于是回表。
2、非聚簇索引
非聚簇索引，也叫辅助索引，在聚簇索引之上创建的索引称之为辅助索引，辅助索引访问数据总是需要二次查找。辅助索引叶子节点存储的不再是行的物理位置，而是主键值。通过辅助索引首先找到的是主键值，再通过主键值找到数据行的数据页，再通过数据页中的Page Directory找到数据行。
Innodb辅助索引的叶子节点并不包含行记录的全部数据，叶子节点除了包含键值外，还包含了相应行数据的聚簇索引键。
辅助索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个辅助索引。在innodb中有时也称辅助索引为二级索引。
3、聚簇索引和非聚簇索引的区别
聚簇索引的叶子节点存放的是主键值和数据行，支持覆盖索引；非聚簇索引（二级索引）的叶子节点存放的是主键值或指向数据行的指针。
由于节子节点(数据页)只能按照一颗B+树排序，故一张表只能有一个聚簇索引。辅助索引的存在不影响聚簇索引中数据的组织，所以一张表可以有多个辅助索引。
覆盖索引（covering index）指一个查询语句的执行只用从索引中就能够取得，不必从数据表中读取。也可以称之为实现了索引覆盖。 当一条查询语句符合覆盖索引条件时，
MySQL只需要通过索引就可以返回查询所需要的数据，这样避免了查到索引后再返回表操作，减少I/O提高效率。 如，在表covering_index_demo中有一个普通索引idx_column1_column2(column1,column2)。当我们通过SQL语句：select column2 from covering_index_demo where column1 = ‘column1_value’;的时候，就可以通过覆盖索引查询，无需回表。
学习参考资料：
1.B站视频MySQL数据库高级
2.关于B树演变参考博客文章原地址
