一、什么是索引

索引是对数据库表中一列或多列的值进行排序的一种结构数据，使用索引可快速访问数据库表中的特定信息。

数据库索引是创建在表的某列上的，并且存储了这一列的所有值。同时存储了指向表中的相应行的指针。

二、索引的分类

唯一索引
唯一索引是不允许其中任何两行具有相同的值的索引。例如，如果在employee表中职员的姓(lname)上创建了唯一索引，则任何两个员工都不能同姓。关键字UNIQUE

主键索引
在数据库关系图中为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。关键字PRIMARY

常规索引
快速定位特定数据

全文索引
全文索引查找的是文本中的关键词，而不是比较索引中的值，关键字FULLTEXT

在InnoDB中根据索引的存储形式，又可以分为一下两种
聚集索引选取规则：
● 如果存在主键，主键索引就是聚集索引
● 如果不存在主键，将使用第一个唯一（UNIQUE）索引作为聚集索引
● 如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引

回表查询
通过二级索引查询到主键，再根据主键去聚集索引中查询一行的数据，称为回表查询

复合引列
可以基于数据库表中的单列或多列创建索引。在业务场景中，如果存在多个查询条件，建议使用联合索引而非单列索引

三、索引的优缺点

优点：
1、通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
2、大大加快数据的检索速度。
3、可以加速表和表之间的连接。
4、在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。
5、通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

缺点：
1、创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
2、索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
3、当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。

四、索引语法

● 创建索引：

CREATE [UNIQUE|FULLTEXT] INDEX index_name ON table_name(index_col_name);

● 查看索引：

SHOW INDEX FROM table_name;

● 删除索引：

DROP INDEX index_name ON table_name;

● 查看索引的使用情况：

SHOW status like ‘Handler_read%'

handler_read_key：这个值越高越好，越高表示使用索引查询到的次数。
handler_read_rnd_next：这个值越高，说明查询低效。

五、索引失效的情况

（1）违背最左前缀法则
如果索引了多列（联合索引），要遵守最左前缀法则。是指查询从索引的最左列开始（索引中的最左列必须存在，跟在SQL语句中的位置无关），并且不跳过索引中的列。如果跳跃某一列，索引将部分失效（后面的字段索引失效），如果缺少了索引的最左列，索引将全部失效。
（2）联合索引中出现范围查询
联合索引中出现范围查询（>，<）,范围查询右侧的列索引失效，所以在业务允许的情况下尽量使用 >= 或 <=
（3）在索引列上进行运算或使用函数
where 子句里对索引列上有数学运算或者使用函数，索引失效。
（4）索引列与条件列字段类型不匹配
如果列类型是字符串，要在条件中将数据使用引号引用起来，否则索引失效。
（5）以%开头的模糊查询
以‘%’开头的like查询会导致索引失效。以‘%’结尾，索引不会失效。
（6）多条件查询使用or连接
多条件查询时使用or连接条件，索引会失效。要想使用or，又想让索引生效，只能将or条件中的每个列都加上索引。
（7）数据分布影响
如果MySQL评估使用全表扫描要比使用索引快，则不使用索引，比如数据量极少的表或者表中的绝大部分数据都满足条件。

六、索引优化方案

（1）索引不要建立在重复值较多的字段上，比如性别
（2）合理使用覆盖索引，减少回表
（3）合理控制索引的数量，一般不超过六个，因为索引在提高查询效率的同时会降低insert和update的效率（可能会重建索引）
（4）避免索引失效
（5）用 force index 命令强制使用某个索引
（6）当字段类型为字符串时，可以只将字符串的一部分前缀做为索引

七、不适合创建索引的情况

1、很少使用或者参考的列不应该创建索引。
2、值分布很稀少的列不适合建索引。比如性别。
3、频繁更新的字段不适合创建索引。
4、定义为text, image和bit数据类型的列不应该增加索引。
5、当修改性能远远大于检索性能时，不应该创建索引。

八、索引的数据结构

首先，数据库索引使用树来存储，因为树的查询效率高，而且二叉查找树还可以保持数据的有序。
为了减少内存的占用，数据库索引是存储在外部磁盘上。Mysql衡量查询效率的标准就是磁盘IO次数。
如果利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。为了提高查询效率，就需要减少磁盘IO数。为了减少磁盘IO的次数，就需要尽量降低树的高度，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好，B树正好符合我们的要求，这也是B树的特征之一。
B树（B类树）的特点就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数。
B树是一种多路平衡查找树，它的每一个节点最多包含K个孩子，k称为B树的阶。k的大小取决于磁盘页的大小。

MySQL的索引是在存储引擎层实现的，不同的存储引擎有不同的结构，主要包含以下几种：

索引结构	描述
B+Tree索引	最常见的索引类型，大部分引擎都支持B+Tree索引
Hash索引	底层数据结构是用哈希表实现的，只支持精确匹配，不支持范围查询
R-tree(空间索引)	空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少
Full-text(全文索引)	是一种通过建立倒排索引，快速匹配文档的方式。类似于Lucene，Solr，Es

一个m阶的B树具有如下几个特征：
1、根结点至少有两个子女。
2、每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m。
3、每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
4、所有的叶子结点都位于同一层。
5、每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B树结构

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

B+树结构

B+树和B树的区别：
1、单一节点存储更多的元素，使得查询的IO次数更少。
2、所有查询都要查找到叶子节点，查询性能稳定。
3、所有叶子节点形成有序链表，便于范围查询。
4、B+树中间节点没有存储数据，只有叶节点存放数据，而B树每个索引节点都会有Data域。

红黑树的特点：
1、节点是红色或黑色。
2、根节点是黑色。
3、每个叶子节点都是黑色的空节点（NIL节点）。
4、每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
6、从根到叶子的最长路径不会超过最短路径的2倍。

红黑树结构：

什么情况下使用红黑树?红黑树和B树使用场合有什么不同？
1、两者都是有序的数据结构，可用作数据容器。
2、红黑树多用在内部排序，即全放在内存中的，微软STL的map和set的内部实现就是红黑树。
3、B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。 在数据较小，可以完全放到内存中时，红黑树的时间复杂度比B树低。反之，数据量较大，外存中占主要部分时，B树因其读磁盘次数少，而具有更快的速度。

注意：
1、B-树和B树是同一概念，翻译不同所致。
2、度数：在树中，每个节点的子节点（子树）的个数就称为该节点的度（degree）。
3、阶数：（Order）阶定义为一个节点的子节点数目的最大值。（自带最大值属性）