1、索引概述

• 索引是一种用于快速查询和检索数据的数据结构，相当于字典的目录，常见的索引结构有B树、B+树和hash等

• 索引的优点：

  • 使用索引可以大大加快数据检索的速度、减少检索的数据量
  • 通过创建唯一性索引，可保证数据库表中每一行数据的唯一性

• 索引的缺点：

  • 创建索引和维护索引需要耗费许多时间，当对表中的数据进行增删改的时候，如果数据有索引，则索引也需要动态地修改，会降低SQL的执行效率
  • 索引需要使用物理文件存储，会耗费一定的空间

注意：大多数情况下，索引查询是比全表扫描要快的，但是如果数据量不大，则使用不一定能够带来很大的提升

2、 索引的底层数据结构

• 哈希表之所以能通过key快速取出对应的value，原因在于哈希算法（散列算法），通过哈希算法，可以快速找到key对应的index和value

hash = hashfunc(key)
index = hash % array_size

• 哈希算法为了解决Hash 冲突 问题，即多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法，链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了解决链表过长的问题而引入了红黑树。
  

• 既然哈希表这么快，为什么MySQL 没有使用其作为索引的数据结构呢？

  • Hash 冲突问题 ：如上已经提及。
  • Hash 索引不支持顺序和范围查询(是最大的缺点， 假如我们要对表中的数据进行排序或者进行范围查询，那 Hash 索引可就不行了。
  • hash结构没有顺序，IO复杂度高。

• 不使用二叉树和红黑树的原因？

  • 二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。
  • 红黑树：树的高度随着数据量增加而增加，IO代价高。

B 树& B+树

• B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。

• 目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。

• B 树& B+树两者的异同：

  • B 树的所有节点既存放键(key) 也存放 数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
  • B 树的叶子节点都是独立的；B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
  • B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定，**任何查找都是从根节点到叶子节点的过程，**叶子节点的顺序检索很明显。
    
    

3、主键类型

1）主键索引(Primary Key)

• 数据表的主键列使用的就是主键索引。
• 一张数据表有只能有一个主键，并且主键不能为 null，不能重复。
• 如果采用 MySQL 的 InnoDB引擎，当没有显示地指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引且不允许存在null值的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。
  

2）二级索引（辅助索引）

• 二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。

二级索引包括唯一索引、普通索引、前缀索引、全文索引。

• 唯一索引(Unique Key) ：唯一索引的属性列不能出现重复的数据，但是允许数据为 NULL，一张表允许创建多个唯一索引。 建立唯一索引的目的大部分时候都是为了该属性列的数据的唯一性，而不是为了查询效率。
• 普通索引(Index) ：普通索引的唯一作用就是为了快速查询数据，一张表允许创建多个普通索引，并允许数据重复和 NULL。
• 前缀索引(Prefix) ：前缀索引只适用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引，相比普通索引建立的数据更小， 因为只取前几个字符。
• 全文索引(Full Text) ：全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。Mysql5.6 之前只有 MYISAM 引擎支持全文索引，5.6 之后 InnoDB 也支持了全文索引。
  

4、聚集索引和非聚集索引

聚集索引

• 聚集索引是索引结构和数据存放在一起的索引，主键索引属于聚集索引。
• 在Mysql中，如果采用InnoDB引擎，则表的.idb文件包含了该表的索引和数据，其表的索引（B+树）的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据
• 聚集索引的优点
  查询速度非常快（B+树是一颗多叉平衡树，叶子节点有序，定位到索引节点，就定位到了数据）
• 聚集索引的缺点
  • 需要依赖于有序的数据，如果索引的数据不是有序的，就需要在插入数据时进行排序，对于类似于字符串或UUID这类又长又难比较的数据，插入和查找的速度都会比较慢
  • 更新代价大，如果要修改索引列的数据，则对应的索引也要修改，所以，对于主键索引来说，主键一般都是不可被修改的

非聚集索引

• 非聚集索引是索引结构和数据分开存储的索引，故二级索引属于非聚集索引
• 二级索引的叶子节点存放的是主键，需要根据主键再回表查询数据
• 优点：
  • 非聚集索引的更新代价比聚集索引要小，其叶子节点是不存放数据的
• 缺点：

  • 依赖于数据的有序性

  • 可能会二次查询（回表），当查到索引对应的指针或主键后，可能会需要根据指针或主键再到数据文件或表中再次查询
    
    

5、覆盖索引

• 覆盖索引即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了，而无需回表查询。

如主键索引，如果一条 SQL 需要查询主键，那么正好根据主键索引就可以查到主键。
再如普通索引，如果一条 SQL 需要查询 name，name 字段正好有索引， 那么直接根据这个索引就可以查到数据，也无需回表。

6、联合索引

使用表中的多个字段创建索引，就是 联合索引，也叫 组合索引 或 复合索引。

7、最左前缀匹配原则

• 在使用联合索引时，MySQL 会根据联合索引中的字段顺序，从左到右依次到查询条件中去匹配，如果查询条件中存在与联合索引中最左侧字段相匹配的字段，则就会使用该字段过滤一批数据，直至联合索引中全部字段匹配完成，或者在执行过程中遇到范围查询，如 >、<、between 和 以%开头的like查询 等条件，才会停止匹配。
• 所以，我们在使用联合索引时，可以将区分度高的字段放在最左边(区分度公式：count(distinct colName)/count(*)，即看某字段不重复的数据量在总数据量中的比重)，这也可以过滤更多数据。

8、创建索引的注意事项

• 1）选择合适的字段创建索引：

  • 不为 NULL 的字段 ：索引字段的数据应该尽量不为 NULL，因为对于数据为 NULL 的字段，数据库较难优化。如果字段频繁被查询，但又避免不了为 NULL，建议使用 0,1,true,false 这样语义较为清晰的短值或短字符作为替代。
  • 被频繁查询的字段 ：我们创建索引的字段应该是查询操作非常频繁的字段。
  • 被作为条件查询的字段 ：被作为 WHERE 条件查询的字段，应该被考虑建立索引。
  • 频繁需要排序的字段 ：索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。
  • 被经常频繁用于连接的字段 ：经常用于连接的字段可能是一些外键列，对于外键列并不一定要建立外键，只是说该列涉及到表与表的关系。对于频繁被连接查询的字段，可以考虑建立索引，提高多表连接查询的效率。

• 2）被频繁更新的字段应该慎重建立索引。

  • 虽然索引能带来查询上的效率，但是维护索引的成本也是不小的。 如果一个字段不被经常查询，反而被经常修改，那么就更不应该在这种字段上建立索引了。

• 3）尽可能的考虑建立联合索引而不是单列索引。

  • 索引是需要占用磁盘空间的，可以简单理解为每个索引都对应着一颗 B+树。如果一个表的字段过多，索引过多，那么当这个表的数据达到一个体量后，索引占用的空间也是很多的，且修改索引时，耗费的时间也是较多的。如果是联合索引，多个字段在一个索引上，那么将会节约很大磁盘空间，且修改数据的操作效率也会提升。

• 4）注意避免冗余索引 。

  • 冗余索引指的是索引的功能相同，能够命中索引(a, b)就肯定能命中索引(a) ，那么索引(a)就是冗余索引。如（name,city ）和（name ）这两个索引就是冗余索引，能够命中前者的查询肯定是能够命中后者的，在大多数情况下，都应该尽量扩展已有的索引而不是创建新索引。

• 5）考虑在字符串类型的字段上使用前缀索引代替普通索引。

  • 前缀索引仅限于字符串类型，较普通索引会占用更小的空间，所以可以考虑使用前缀索引带替普通索引。

9、MySQL 如何为表字段添加索引？

• 添加主键索引（PRIMARY KEY）

ALTER TABLE `table_name` ADD PRIMARY KEY ( `column` )

• 添加唯一索引（UNIQUE ）

ALTER TABLE `table_name` ADD UNIQUE ( `column` )

• 添加普通索引（INDEX ）

ALTER TABLE `table_name` ADD INDEX index_name ( `column` )

• 添加全文索引（FULLTEXT ）

ALTER TABLE `table_name` ADD FULLTEXT ( `column`)

• 添加前缀索引(以前m位字符来创建)

ALTER TABLE `table_name` ADD index ( column(m) )

• 添加组合索引

ALTER TABLE `table_name` ADD INDEX index_name ( `column1`, `column2`, `column3` )

参考资料：
图解 MySQL 索引：B-树、B+树
Mysql面试总结