MySQL --- 索引机制

说说你对 MySQL 索引的理解？

• 索引是一种用于快速查询和检索数据的数据结构。常见的索引结构有: B 树， B+树和 Hash。
  
• 索引的作用就相当于目录的作用，可以类比字典、 火车站的车次表、图书的目录等 。
  
• 索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。
  
• 索引本身也很大，不可能全部存储在内存中，一般以索引文件的形式存储在磁盘上，(InnoDB数据表上的索引是表空间的一个组成部分)，它们包含着对数据表里所有记录的引用指针。

索引有哪些优缺点？

优势：

• 效率：大大提高数据检索效率（减少了检索的数据量），降低数据库IO成本，这也是创建索引的最主要原因；
  
• 性能：降低数据排序的成本，降低CPU的消耗，提高系统性能；被索引的列会自动进行排序，包括【单列索引】和【组合索引】，只是组合索引的排序要复杂一些。如果按照索引列的顺序进行排序，对应order by语句来说，效率就会提高很多。
  

劣势：

• 空间方面：索引也是一张表，保存了主键和索引字段，并指向实体表的记录，所以索引也需要占用内存（物理空间）/磁盘空间。
  
• 时间方面：创建索引和维护索引要耗费时间，具体地，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，会降低增/改/删的执行效率；

MySQL有哪几种索引类型？（或者说索引是怎么实现的？）

• 从存储数据结构上来划分：B-Tree索引（B-Tree或B+Tree索引），Hash索引，full-index全文索引，R-Tree索引。这里所描述的是索引存储时保存的形式，
  
• 从物理存储角度划分： 聚集索引，即数据文件本身就是主键索引文件（InnoDB）。非聚集索引（辅助索引），即索引文件与数据文件是分离的（MyISAM），聚集索引和非聚集索引都是B+树结构。
  
• 从逻辑角度划分：

• 普通索引（单列索引）：每个索引只包含单个列，一个表可以有多个单列索引，仅加速查询；
• 唯一索引：加速查询 + 列值唯一（可以有null）
• 主键索引：加速查询 + 列值唯一（不可以有null）+ 表中只有一个，在 mysql 的 InnoDB 的表中，当没有显示的指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。
• 组合/复合索引（多列索引）：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并（即使用多个单列索引组合搜索）

• 补充：主键与唯一索引的区别：
  

• 主键是一种约束，目的是对这个表的某一列进行限制；唯一索引是一种索引，目的是为了加速查询；
• 主键列不允许为空值，而唯一索引列可以为空值（null）
• 一个表中最多只能有一个主键，但是可以包含多个唯一索引，  主键一定是唯一性索引，唯一性索引并不一定就是主键

Mysql目前主要有以下几种结构的索引类型：B+Tree 索引、哈希索引、全文索引（full-index）与空间数据索引（R-Tree）

• B+Tree 索引：是大多数 MySQL 存储引擎的默认索引类型，不需进行全表扫描，只需对树进行搜索，所以查找速度快很多； B+ Tree 的有序性，所以除了用于查找，还可以用于排序和分组。
  
• 哈希索引：哈希索引能以 O(1) 时间进行查找，一次定位，不需要像树形索引逐层查找，具有极高的效率。哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。但是失去了有序性：

• 对排序与组合索引效率不高；
• 只支持精确查找（等值查询，如=、in()、<=>），无法用于部分查找和范围查找。

• InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。
  
• 全文索引：MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。查找条件使用 MATCH AGAINST，而不是普通的 WHERE。全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射。InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。
  
• 空间数据索引：MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。必须使用 GIS 相关的函数来维护数据。

为什么索引默认用 B+树，而不用B树、二叉树、hash和红黑树呢？

为什么不用B-tree：

• B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针（B树每个节点都存储数据，B+树只有叶子节点才存储节点），所以查找相同数据量的情况下，B树的高度更高，IO更频繁。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。
  
• B+树区间查询更高效：由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可（叶子节点使用双向链表连接）。但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来找，所以B+树更加适合在区间查询的情况，通常B+树用于数据库索引。
  

为什么不用Hash方式呢？

• hash索引不适合区间查询：因为Hash索引底层是哈希表，哈希表是一种以key-value存储数据的结构，只适合等值查询（等值查询效率高），如=、in()、<=>:（严格比较两个NULL值是否相等，都为null，返回1，否则返回0），多个数据在存储关系上是完全没有任何顺序关系的（数据无序），所以对于区间查询是无法直接通过索引查询的，就需要全表扫描，即不支持范围查询 。
  
• 哈希碰撞：哈希索引不支持多列联合索引的最左匹配规则，如果有大量重复键值得情况下，哈希索引的效率会很低，因为存在哈希碰撞问题。
  

二叉树： 树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。

红黑树/AVL树： 树的高度随着数据量增加而增加，IO代价高。如果存在频繁的插入、删除操作，那么AVL树自平衡，红黑树的左旋和右旋等比较影响性能。

拓展：磁盘预读原理

1.文件很大，不可能全部存储在内存中，故要存储到磁盘上

2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数（为什么使用B-/+Tree，还跟磁盘存取原理有关。）

3.局部性原理与磁盘预读，预读的长度一般为页（page）的整倍数（在许多操作系统中，页得大小通常为4k）

4.数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，(由于节点中有两个数组，所以地址连续)。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性

聚集索引与非聚集索引的区别？

首先mysql聚簇和非聚簇索引都是B+树结构。

聚集/聚簇索引(Innodb默认)：即索引结构和数据一起存放的索引，主键索引属于聚集索引。数据的物理存放顺序与索引的顺序是一致的，一个表只能有一个聚集索引**。在 Mysql 中，InnoDB 引擎的表的 .ibd文件就包含了该表的索引和数据，对于 InnoDB 引擎表来说，该表的索引(B+树)的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。

• 聚集索引的优点：聚集索引适合区间查询（数据按照大小排序的），数据查询性能比较高，相比非聚簇索引需要第二次查询（非覆盖索引的情况下）效率要高。因为整个 B+树本身就是一颗多叉平衡树，叶子节点也都是有序的，定位到索引的节点，就相当于定位到了数据。
  
• 聚集索引的缺点：
  

1. 依赖于有序的数据 ：因为 B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似于字符串或 UUID 这种又长又难比较的数据，插入或查找的速度肯定比较慢。
   
2. 维护代价大 ： 如果对索引列的数据被修改时，那么对应的索引也将会被修改， 而且聚集索引的叶子节点还存放着数据，修改代价肯定是较大的， 所以对于主键索引来说，主键一般都是不可被修改的。
   

非聚集索引：非聚集索引即索引结构和数据分开存放的索引。二级索引属于非聚集索引。表中记录的物理顺序与键值的索引顺序不同。这也是非聚集索引与聚集索引的根本区别。注意：非聚集索引的叶子节点并不一定存放数据的指针（行地址）， 因为二级索引的叶子节点就存放的是主键，根据主键再回表查数据。MYISAM 引擎的表的.MYI 文件包含了表的索引， 该表的索引(B+树)的每个叶子非叶子节点存储索引， 叶子节点存储索引和索引对应数据的指针，指向.MYD 文件的数据。ps：类似先找到书的目录，再找到对应的页码。

• 非聚集索引的优点：更新代价比聚集索引要小 。因为非聚集索引的叶子节点是不存放数据的。
  
• 非聚集索引的缺点：
  

1. 跟聚集索引一样，非聚集索引也依赖于有序的数据
   
2. 可能会二次查询(回表) :这应该是非聚集索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

非聚簇索引一定会回表查询（覆盖索引）吗？

答：不一定，如果涉及到查询语句所要求的字段全部命中了索引，那么就不必再进行回表查询。

试想一种情况，用户准备使用 SQL 查询用户名，而用户名字段正好建立了索引。

SELECT name FROM table WHERE name='guang19';

那么这个索引的 key 本身就是 name，查到对应的 name 直接返回就行了，无需回表查询。

覆盖索引：需要查询的字段值正好是索引的字段（或者说索引字段已经覆盖了我们的查询需求），那么直接根据该索引，就可以查到数据了， 而无需回表查询。

• 就是select的数据列只用从索引中就能够取得，不必读取数据行，MySQL可以利用索引返回select列表中的字段，而不必根据索引再次读取数据文件，换句话说查询列要被所建的索引覆盖。
• 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
• 判断标准：使用explain，可以通过输出的extra列来判断，对于一个索引覆盖查询，显示为using index，MySQL查询优化器在执行查询前会决定是否有索引覆盖查询。

我们知道在 InnoDB 存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢覆，覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！

当然，索引字段的维护总是有代价的。因此，在建立冗余索引来支持覆盖索引时就需要权衡考虑了。

explain：SQL语句的执行计划

我们常常用到explain这个命令来查看一个这些SQL语句的执行计划，查看该SQL语句有没有使用上了索引，有没有做全表扫描，这都可以通过在SQL语句前面加explain命令来查看。

id:选择标识符

select_type:表示查询的类型。

table:输出结果集的表

partitions:匹配的分区

type:表示表的连接类型

possible_keys:表示查询时，可能使用的索引

key:表示实际使用的索引

key_len:索引字段的长度

ref:列与索引的比较

rows:扫描出的行数(估算的行数)

filtered:按表条件过滤的行百分比

Extra:执行情况的描述和说明

InnoDB引擎中的索引策略，了解过吗？

InnoDB主键索引与辅助索引的结构：InnoDB引擎索引结构的叶子节点的数据域，存放的就是实际的数据记录（对于主索引，此处会存放表中所有的数据记录；对于辅助索引此处会引用主键，检索的时候通过主键到主键索引中找到对应数据行），或者说，InnoDB的数据文件本身就是主键索引文件，这样的索引被称为"“聚簇索引”，一个表只能有一个聚簇索引。

InnoDB 索引结构需要注意的点：

1. 数据文件本身就是索引文件
2. 表数据文件本身就是按 B+Tree 组织的一个索引结构文件
3. 聚集索引中叶节点包含了完整的数据记录
4. InnoDB 表必须要有主键，并且推荐使用整型自增主键

正如我们上面介绍 InnoDB 存储结构，索引与数据是共同存储的，不管是主键索引还是辅助索引，在查找时都是通过先查找到索引节点才能拿到相对应的数据。

• 如果我们在设计表结构时没有显式指定索引列的话，MySQL 会从表中选择数据不重复的列建立索引
  
• 如果没有符合的列，则 MySQL 自动为 InnoDB表生成一个隐含字段作为主键，并且这个字段长度为6个字节，类型为整型。

创建索引的方式有哪些？

创建索引有三种方式：

• 在执行CREATE TABLE时创建索引

CREATE TABLE user_index2 (
    id INT auto_increment PRIMARY KEY,
    first_name VARCHAR (16),
    last_name VARCHAR (16),
    id_card VARCHAR (18),
    information text,
    KEY name (first_name, last_name),
    FULLTEXT KEY (information),
    UNIQUE KEY (id_card)
);

• 使用ALTER TABLE命令去增加索引。

ALTER TABLE table_name ADD INDEX index_name (column_list);

ALTER TABLE用来创建普通索引、UNIQUE索引或PRIMARY KEY索引。

其中table_name是要增加索引的表名，column_list指出对哪些列进行索引，多列时各列之间用逗号分隔。

索引名index_name可自己命名，缺省时，MySQL将根据第一个索引列赋一个名称。另外，ALTER TABLE允许在单个语句中更改多个表，因此可以在同时创建多个索引

• 使用CREATE INDEX命令创建。

CREATE INDEX index_name ON table_name (column_list);

创建索引时原则有哪些？需要注意什么？

索引创建的原则：

• 最左前缀匹配原则：假设创建的联合索引由三个字段组成如下。那么当查询的条件有为:num / (num AND name) / (num AND name AND age)时，索引才生效。所以在创建联合索引时，尽量把查询最频繁的那个字段作为最左(第一个)字段。查询的时候也尽量以这个字段为第一条件。
  ps：联合索引各字段的顺序？第一原则，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
  ps：如果既有联合查询，又有基于 a、b 各自的查询呢？查询条件里面只有 b 的语句，是无法使用 (a,b) 这个联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护 (a,b)、(b) 这两个索引。这时候需要考虑的原则就是索引空间问题。
  ps：如果不满足最左前缀的部分怎么办？在 MySQL 5.6 之前，只能进行回表。到主键索引上找出数据行，再对比字段值。而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

ALTER TABLE table ADD INDEX index_name (num,name,age)

• 单列索引：由一列属性组成的索引
  
• 联合/组合/复合索引（多列索引）：联合索引即由多列属性组成索引。基于多个字段而创建的索引就称为组合索引，组合索引的使用要遵从最左前缀。在最左前缀原则中，范围查询会导致组合索引半生效，where子句有or出现还是会遍历全表。
  具体原因为:
  MySQL使用索引时需要索引有序，假设现在建立了"name，age，school"的联合索引，那么索引的排序为: 先按照name排序，如果name相同，则按照age排序，如果age的值也相等，则按照school进行排序。
  当进行查询时，此时索引仅仅按照name严格有序，因此必须首先使用name字段进行等值查询，之后对于匹配到的列而言，其按照age字段严格有序，此时可以使用age字段用做索引查找，以此类推。因此在建立联合索引的时候应该注意索引列的顺序，一般情况下，将查询需求频繁或者字段选择性高的列放在前面。此外可以根据特例的查询或者表结构进行单独的调整。
  

创建索引的注意点：

• 遵守最左前缀原则
• 选择合适的字段

• 非空字段：索引字段的数据应该尽量不为 NULL，因为对于数据为 NULL 的字段，数据库较难优化。如果字段频繁被查询，但又避免不了为 NULL，建议使用 0,1,true,false 这样语义较为清晰的短值或短字符作为替代。
• 被频繁查询的字段：创建索引的字段应该是查询操作非常频繁的字段，但注意慎重创建索引，不被经常查询的字段没必要建立索引，因为维护索引的成本也不小。
• 被作为条件查询的字段：被作为 WHERE 条件查询的字段，应该被考虑建立索引。
• 被经常频繁用于连接的字段：经常用于连接的字段可能是一些外键列，对于外键列并不一定要建立外键，只是说该列涉及到表与表的关系。对于频繁被连接查询的字段，可以考虑建立索引，提高多表连接查询的效率。
• 考虑扩展而非创建索引：冗余索引指的是索引的功能相同，如（name,city ）和（name ）这两个索引就是冗余索引，能够命中前者的查询肯定是能够命中后者的。在大多数情况下，都应该尽量扩展已有的索引而不是创建新索引。
• 尽可能建立联合索引非单列索引：因为索引是需要占用磁盘空间的。如果一个表的字段过多，索引过多，那么当这个表的数据达到一个体量后，索引占用的空间也是很多的，且修改索引时，耗费的时间也是较多的。如果是联合索引，多个字段在一个索引上，那么将会节约很大磁盘空间，且修改数据的操作效率也会提升。
• 考虑在字符串类型的字段上使用前缀索引代替普通索引：前缀索引仅限于字符串类型，较普通索引会占用更小的空间，所以可以考虑使用前缀索引带替普通索引。

ps：联合索引与单列索引的区别：

• 创建联合索引时，要考虑列的顺序，如果使用前几列查询，联合索引有效，后几列查询，联合索引无效。
  
• 联合索引使用最左前缀原则，例如A,B两个字段都会在查询中用到，但A使用的频率更高，就将A作为联合索引的第一个字段，放在最左边。
  
• 当存在多个单列索引可以用时，mysql会根据查询优化策略选择其中一个单列索引，并不是每个单列索引都生效。
  
• 当同时存在单列索引和联合索引，mysql会根据查询优化策略选择其中一个索引。
  
• 如果where中的关系是or，索引不生效。

为什么使用自增主键作为索引？那为什么推荐使用整型自增主键而不是选择UUID？

结合B+Tree的特点，自增主键是连续的，在插入过程中尽量减少页分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少页分裂和移动的频率。

• UUID（元素唯一识别码，不会重复）是字符串，比整型消耗更多的存储空间；
  
• 在B+树中进行查找时需要跟经过的节点值比较大小，整型数据的比较运算比字符串更快速；
  
• 自增的整型索引在磁盘中会连续存储，在读取一页数据时也是连续；UUID是随机产生的，读取的上下两行数据存储是分散的，不适合执行where id > 5 && id < 20的条件查询语句。
  
• 在插入或删除数据时，整型自增主键会在叶子结点的末尾建立新的叶子节点，不会破坏左侧子树的结构；UUID主键很容易出现这样的情况，B+树为了维持自身的特性，有可能会进行结构的重构，消耗更多的时间。

使用索引查询一定能提高查询的性能吗？

通常通过索引查询数据比全表扫描要快。但是我们也必须注意到它的代价。

索引需要空间来存储，也需要定期维护， 每当有记录在表中增减或索引列被修改时，索引本身也会被修改。 这意味着每条记录的INSERT，DELETE，UPDATE将为此多付出4，5 次的磁盘I/O。 因为索引需要额外的存储空间和处理，那些不必要的索引反而会使查询反应时间变慢。使用索引查询不一定能提高查询性能，索引范围查询(INDEX RANGE SCAN)适用于两种情况:

• 基于一个范围的检索，一般查询返回结果集小于表中记录数的30%。
  
• 基于非唯一性索引的检索。

MySql如何使用索引？

• 单列索引的使用。（1）多索引时，不存在主键索引的话，那么就会使用该使用的索引（注：如果通过其中的部分索引就能准确定位的话，那么其余的索引就不再被使用）（2）多个索引时，先使用哪个索引后使用哪个索引，是由MySQL的优化器经过一些列计算后作出的抉择。

ps：模糊查询时，%如果在前面，那么不会使用索引。在实际使用时，如果涉及到多列，我们一般都不会将这些列一 一创建为单列索引，而是将这些列创建为组合索引。

• 组合索引的使用。（1）如果是部分满足最左原则，满足部分使用组合索引；（2）不符合索引自身规范（比如使用>）（3）特殊：当无需回表时，不遵循最左原则也是会走组合索引

ps：一般必须符合最左前缀原则：假设组合索引为：a,b,c的话；那么当SQL中对应有：a或a，b或a，b，c的时候，可称为完全满足最左原则；当SQL中查询条件对应只有a，c的时候，可称为部分满足最左原则；当SQL中没有a的时候，可称为不满足最左原则。注：MySQL5.7开始，会自动优化，符合最左前缀原则。

查询语句是否用到索引的分析?

在查询语句前面加上explain（explain执行计划）

我们只需要注意一个最重要的type 的信息很明显的体现是否用到索引。一般来说，得保证查询至少达到range级别，最好能达到ref，否则就可能会出现性能问题。Key为实际使用的索引。

UUID和int自增主键的区别

UUID：由于UUID是随机生成的 插入时位置具有一定的不确定性，无序插入，会存在许多内存碎片，内存空间的占用量也会比自增主键大，区间查找也没自增主键性能优

• 优点：避免重复，便于后续的划分；

自增主键：在进行数据库插入时，位置相对固定（B+树中的右下角）增加数据插入效率，减少插入的磁盘IO消耗，每页的空间在填满的情况下再去申请下一个空间，底层物理连续性更好，能更好的支持区间查找

总之，访问量大时，用UUID；访问量小时，用自增ID；

以上仅供学习使用

参考鸣谢：

http://cyc2018.gitee.io/cs-notes/#/notes/MySQL?id=myisam

https://www.nowcoder.com/discuss/639644type=post&order=time&pos=&page=1&channel=-1&source_id=search_post_nctrack

https://gitee.com/SnailClimb/JavaGuide/blob/master/docs/database/MySQL.md