什么是索引

索引，类似于书籍的目录,想要找到一本书的某个特定的主题,需要先找到书的目录,定位到对应的页码.
MySQL中存储引擎使用类似的方式进行查询,先去索引中查询对应的值,然后根据匹配的索引找到对应的数据行.

索引有什么好处

    1. 提高数据的检索速度,降低数据库IO成本: 使用索引的意义就是通过缩小表中需要查询的字段的记录的数目从而加快索引的速度.
    1. 降低数据排序的成本,降低CPU消耗: 索引之所以查的快,是因为先将数据排好序,若该字段正好需要排序,则正好降低了排序的成本.

索引有什么坏处

    1. 占用存储空间: 索引实际上也是一张表,记录了主键与字段索引,一般以索引文件的形式存储在磁盘上.

    1. 降低更新表的速度: 表的数据发生了变化,对应的索引也需要一起变更,从而降低表的更新速度.

      否则索引指向的物理数据可能不对,这也是索引失效的原因之一.

索引的使用场景

    1. 对非常小的表,大部分情况下全表扫描效率更高.
    1. 对中大型表,索引非常有效.
    1. 特大型表,建立和使用索引的代价随着增长,可以使用分区技术来解决.

实际场景下，MySQL 分区表很少使用，原因可以看看 《互联网公司为啥不使用 MySQL 分区表？》 文章。对于特大型的表，更常用的是“分库分表”，目前解决方案有 Sharding Sphere、MyCAT 等等。

索引的类型

索引都是实现在存储引擎层的,主要有六种类型:

    1. 普通索引: 最基本的索引,没有任何约束.
    1. 唯一索引: 与普通索引类似,但是具有唯一性约束.
    1. 主键索引: 特殊的唯一索引,不允许有空值.
    1. 复合索引: 将多个列组合在一起创建索引,可以覆盖多个列.
    1. 外键索引: 只有InnoDB类型的表才可以使用外键索引,保证数据的唯一性、完整性和实现级联操作.
    1. 全文检索: MySQL自带的全文索引只能适用于InnoDB、MyISAM,并且只能对英文进行全文检索,一般使用全文索引引擎.

常用的全文索引引擎的解决方案有 Elasticsearch、Solr 等等。最为常用的是 Elasticsearch 。
具体的使用，可以看看 《服务端指南 数据存储篇 | MySQL（03） 如何设计索引》 。

MySQL索引的创建原则

    1. 最适合索引出现的列是出现在WHERE子句中的列,或连接子句中的列,而不是出现在SELECT关键字后的列.
    1. 索引列的基数越大,索引的效果越好.

具体为什么，可以看看如下两篇文章：

  • 《MySQL 索引基数》 理解相对简单
  • 《低基数索引为什么会对性能产生负面影响》 写的更原理，所以较为难懂。
      1. 根据情创建复合索引,复合索引可以提高查询效率.
  • 因为复合索引的基数更大.
      1. 避免创建过多的索引,索引会额外占用磁盘空间,降低写操作的效率.
      1. 主键尽可能的选择较短的数据类型,可以有效的减少索引的磁盘占用来提高查询效率.
      1. 对字符串进行索引,应该定制一个前缀长度,可以节省大量的索引空间.

MySQL索引的使用注意事项

以下情况下将导致引擎放弃使用索引而使用全表扫描:

    1. 在WHERE子句中使用!=或者<>操作符。
      • 注意：IS NULL 也是不可以使用索引的。
    1. 在WHERE子句使用OR作为连接条件。
    1. 在WHERE子句中对字段进行函数操作。
    1. 在WHERE子句中对字段进行表达式操作。
    1. 在WHERE子句的=左边进行函数、算术运算或是其他表达式运算
    1. 复合函数不遵循前缀原则。
    1. 如果MySQL评估使用索引比全表扫描更慢，会放弃使用索引。如果此时想要使用索引，可以在语句中添加强制索引。
    1. 列类型是字符串类型，查询时一定要给值加引号，否者索引失效（MySQL会进行数据类型转换）。
    1. LIKE查询，%不能在前，因为无法使用索引。如果需要模糊匹配，可以使用全文索引。

关于这块，可以看看 《服务端指南 数据存储篇 | MySQL（04） 索引使用的注意事项》 文章，写的更加细致。

如何查看一个查询用到了那个索引（SQL执行计划）

EXPLAIN 显示了 MYSQL 如何使用索引来处理 SELECT 语句以及连接表,可以帮助选择更好的索引和写出更优化的查询语句。
使用方法，在 SELECT 语句前加上 EXPLAIN 就可以了。 《MySQL explain 执行计划详细解释》。

MySQL的两种索引方式

1. B-Tree索引

B-Tree 是为磁盘等外存储设备设计的一种平衡查找树。因此在讲 B-Tree 之前先了解下磁盘的相关知识。

  • 系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

  • InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB 存储引擎中默认每个页的大小为 16 KB，可通过参数 innodb_page_size 将页的大小设置为 4K、8K、16K ，在 MySQL 中可通过如下命令查看页的大小：

    1. mysql> show variables like 'innodb_page_size';

  • 而系统一个磁盘块的存储空间往往没有这么大，因此 InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB 。InnoDB 在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘 I/O 次数，提高查询效率。

B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组 [key, data] ，key 为记录的键值，对应表中的主键值，data 为一行记录中除主键外的数据。对于不同的记录，key值互不相同。

一棵m阶的B-Tree有如下特性：

  1. 每个节点最多有 m 个孩子。
    • 除了根节点和叶子节点外，其它每个节点至少有 Ceil(m/2) 个孩子。
    • 若根节点不是叶子节点，则至少有 2 个孩子。
  2. 所有叶子节点都在同一层，且不包含其它关键字信息。
  3. 每个非叶子节点包含 n 个关键字信息（P0,P1,…Pn, k1,…kn）
    • 关键字的个数 n 满足：ceil(m/2)-1 <= n <= m-1
    • ki(i=1,…n) 为关键字，且关键字升序排序。
    • Pi(i=0,…n) 为指向子树根节点的指针。P(i-1) 指向的子树的所有节点关键字均小于 ki ，但都大于 k(i-1) 。

B-Tree 中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个 3 阶的 B-Tree：
MySQL索引 - 图1

  • 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的 key 和三个指向子树根节点的 point ，point 存储的是子节点所在磁盘块的地址。两个 key 划分成的三个范围域，对应三个 point 指向的子树的数据的范围域。
  • 以根节点为例，key 为 17 和 35 ，P1 指针指向的子树的数据范围为小于 17 ，P2 指针指向的子树的数据范围为 [17~35] ，P3 指针指向的子树的数据范围为大于 35 。

模拟查找 key 为 29 的过程：

  • 1、根据根节点找到磁盘块 1 ，读入内存。【磁盘I/O操作第1次】
  • 2、比较 key 29 在区间（17,35），找到磁盘块 1 的指针 P2 。
  • 3、根据 P2 指针找到磁盘块 3 ，读入内存。【磁盘I/O操作第2次】
  • 4、比较 key 29 在区间（26,30），找到磁盘块3的指针P2。
  • 5、根据 P2 指针找到磁盘块 8 ，读入内存。【磁盘I/O操作第3次】
  • 6、在磁盘块 8 中的 key 列表中找到 eky 29 。

分析上面过程，发现需要 3 次磁盘 I/O 操作，和 3 次内存查找操作。由于内存中的 key 是一个有序表结构，可以利用二分法查找提高效率。而 3 次磁盘 I/O 操作是影响整个 B-Tree 查找效率的决定因素。B-Tree 相对于 AVLTree 缩减了节点个数，使每次磁盘 I/O 取到内存的数据都发挥了作用，从而提高了查询效率。

B+Tree 有哪些索引类型？

在 B+Tree 中，根据叶子节点的内容，索引类型分为主键索引和非主键索引。

  • 主键索引的叶子节点存的数据是整行数据( 即具体数据 )。在 InnoDB 里，主键索引也被称为聚集索引（clustered index）。
  • 非主键索引的叶子节点存的数据是整行数据的主键，键值是索引。在 InnoDB 里，非主键索引也被称为辅助索引（secondary index）。

辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，需要进过两步：

  • 首先，InnoDB 存储引擎会遍历辅助索引找到主键。
  • 然后，再通过主键在聚集索引中找到完整的行记录数据。

另外，InnoDB 通过主键聚簇数据，如果没有定义主键，会选择一个唯一的非空索引代替，如果没有这样的索引，会隐式定义个主键作为聚簇索引。
再另外，可能有胖友有和艿艿的一样疑惑，在辅助索引如果相同的索引怎么存储？最终存储到 B+Tree 非子节点中时，它们对应的主键 ID 是不同的，所以妥妥的。如下图所示：
MySQL索引 - 图2

聚簇索引的注意点有哪些？

聚簇索引表最大限度地提高了 I/O 密集型应用的性能，但它也有以下几个限制：

    1. 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于 InnoDB 表，我们一般都会定义一个自增的 ID 列为主键。
      • 关于这一点，可能面试官会换一个问法。例如，为什么主键需要是自增 ID ，又或者为什么主键需要带有时间性关联。
    1. 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB 表，我们一般定义主键为不可更新。
      • MySQL 默认情况下，主键是允许更新的。对于 MongoDB ，其 主键是不允许更新的。
    1. 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。
      • 当然，有一种情况可以无需二次查找，基于非主键索引查询，但是查询字段只有主键 ID ，那么在二级索引中就可以查找到。
    1. 主键 ID 建议使用整型。因为，每个主键索引的 B+Tree 节点的键值可以存储更多主键 ID ，每个非主键索引的 B+Tree 节点的数据可以存储更多主键 ID 。

什么是索引的最左匹配特性？

当 B+Tree 的数据项是复合的数据结构，比如索引 (name, age, sex) 的时候，B+Tree 是按照从左到右的顺序来建立搜索树的。

  • 比如当 (张三, 20, F) 这样的数据来检索的时候，B+Tree 会优先比较 name 来确定下一步的所搜方向，如果 name 相同再依次比较 age 和 sex ，最后得到检索的数据。
  • 但当 (20, F) 这样的没有 name 的数据来的时候，B+Tree 就不知道下一步该查哪个节点，因为建立搜索树的时候 name 就是第一个比较因子，必须要先根据 name 来搜索才能知道下一步去哪里查询。
  • 比如当 (张三, F) 这样的数据来检索时，B+Tree 可以用 name 来指定搜索方向，但下一个字段 age 的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是 F 的数据了。

这个是非常重要的性质，即索引的最左匹配特性。

MyISAM 索引实现？

MyISAM 索引的实现，和 InnoDB 索引的实现是一样使用 B+Tree ，差别在于 MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

MyISAM 索引与 InnoDB 索引的区别？

  • InnoDB 索引是聚簇索引，MyISAM 索引是非聚簇索引。
  • InnoDB 的主键索引的叶子节点存储着行数据，因此主键索引非常高效。
  • MyISAM 索引的叶子节点存储的是行数据地址，需要再寻址一次才能得到数据。
  • InnoDB 非主键索引的叶子节点存储的是主键和其他带索引的列数据，因此查询时做到覆盖索引会非常高效。