1. 谈谈你对索引的理解？

索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。索引的出现是提高了数据的查询效率，但同时索引也带来很多负面影响：

  1. 创建索引和维护索引需要耗费时间，对表进行增删改查的时候也要动态维护，这个时间耗费随着数据量的增加而增加。
  2. 一般来说索引本身也很大，不可能全部存储在内存中，因此每个索引也需要占用物理空间。索引往往是存储在磁盘上的文件中的（可能存储在单独的索引文件中（InnoDB），也可能和数据一起存储在数据文件中（MyIsaM））。

索引有多大？ 假设有 1 亿个节点，使用 B+ 树结构的存储引擎需要查询多少次呢，显然最多为 $ log_2 {1亿} = 27 $ 次，这样的速度是非常快了。但是又出现一个新的问题，假设每个节点为 16 byte，则 1 亿个节点需要占用 1.5G 内存！这还只是一个索引，所以我们只能将它放在磁盘中。

2. 为什么要使用索引？

避免使用全表扫描，提升检索效率。

如果不使用索引，使用全表扫描。存储的最小单位是块或者页（由多行数据组成），将所有块加载进来，然后逐个块进行轮询，找到我们要的目标并返回。这种方法只适用于小数据量，如果是在数据量很大的表里，这种方法不适用。这时索引就派上用场了。

可以对一张表创建多个索引。索引的优点是提高了查询效率，缺点是在插入、更新和删除记录时，需要同时修改索引，因此，索引越多，插入、更新和删除记录的速度就越慢。数据库索引对于用户和应用程序来说都是透明的。

3. 索引的类型

3.1 主键索引

主键索引列中的值必须是唯一的，不允许有空值。

与主键索引对应的是辅助索引（普通索引），当键值不是主键时，就是辅助索引（普通索引）。因此，主键索引只能有一个，而辅助索引（普通索引）可以有很多个。

3.2 普通索引

MySQL 中基本的索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值。

3.3 唯一索引

索引列中的值必须是唯一的，但是允许为空值。

3.4 全文索引

只能在文本类型CHAR, VARCHAR, TEXT类型字段上创建全文索引。字段长度比较大时，如果创建普通索引，在进行like模糊查询时效率比较低，这时可以创建全文索引。

3.5 空间索引

MySQL在5.7之后的版本支持了空间索引，而且支持OpenGIS几何数据模型。MySQL在空间索引这方面遵循OpenGIS几何数据模型规则。

3.6 前缀索引

在文本类型如CHAR, VARCHAR, TEXT类型字段上创建索引时，可以指定索引列的长度，但是数值类型不能指定。

3.7 其他（按照索引列数量分类）

单列索引和组合索引。组合索引的使用，需要遵循最左前缀匹配原则（最左匹配原则）。一般情况下在条件允许的情况下使用组合索引替代多个单列索引使用。

4. 索引是建立的越多越好吗？

不是。

  • 数据量小的表不需要建立索引，建立索引反而会增加额外的索引开销。
  • 除了数据表占数据空间之外，每一个索引还要占一定的物理空间。如果要建立聚簇索引，那么需要的空间就会更大。
  • 当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

    5. 索引的数据结构

    5.1 二叉查找树（BST）

    不合适。每进行一次查找，就会产生一次 IO，每个节点只有两个孩子，树的深度一般都会很深，IO 的次数会很多，这样一来检索的性能就很低了。而且二叉查找树比较不稳定，容易退化成链表。

    5.2 平衡二叉树（AVL）

    不合适。AVL 的问题是：
  1. 时间复杂度和树高相关。每个节点的读取，都对应一次磁盘 IO 操作，树的高度就等于每次查询数据时磁盘 IO 操作的次数。假设磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（比如1百万的数据量，需要log2n = 20次磁盘IO，时间20*10*0.001=0.2s）
  2. 平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

    5.3 B树（改造二叉树）

    MySQL 的数据是存储在磁盘中的，而磁盘 IO 操作是非常耗时的，而访问二叉树的每个节点就会发生一次 IO，因此我们优化的重点就是尽量降低树的高度。

InnoDB 引擎一次 IO 会读取一页（默认一页 16K 的数据量），假设二叉树一次 IO 有效数据量只有16个字节（每个节点存储一个8字节的 key 和 2 个4字节的指针），那么这样的空间利用率是非常低的。为了最大化利用一次 IO 空间，一个简单的想法是在每个节点存储尽可能多的数据。每个节点其实可以存储 1000 个索引（16k / 16 = 1000），这样就将二叉树改造成了多叉树，将树从高瘦改造成矮胖。这样 IO 次数变少了，查询效率也就提高了。
数据库索引 - 图1
如上图所示的结构就是 B树，它是一种多叉平衡查找树，有以下主要特点：

  1. B树的节点中存储着多个元素，每个内节点有多个分叉。
  2. 节点中的元素包含键值和数据，节点中的键值按从小到大的顺序排列。
  3. 父节点当中的元素不会出现在子节点中。
  4. 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

相比平衡二叉树树，在查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于我们的比较是在内存中进行的，比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。但 B树 仍然存在可以优化的地方：

  1. B树 不支持范围查询的快速查找。

  2. 如果 data 存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘 IO 次数就会变多。

    5.4 B+树（改造B树）

    B+树 作为 B树 的升级版，解决了 B树 存在的两个问题，其区别于 B树 的特点是：

  3. B+ 树只有叶子节点才会存储数据，非叶子节点只存储键值。

  4. 叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。
  5. 由于 B+树 的非叶子节点不存储数据，所以它们能够存储更多的键值，所以 B+树 更矮，需要的 I/O 次数更少。

数据库索引 - 图2

先看一个等值查询的例子，假如我们查询值等于9的数据。查询路径磁盘块1 -> 磁盘块2 -> 磁盘块6。 第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，9<15，走左路，到磁盘寻址磁盘块2。 第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<9<12，到磁盘中寻址定位到磁盘块6。 第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头遍历比较，在第三个索引中找到9，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。（这里需要区分的是在 InnoDB 中 data 存储的为行数据，而 MyIsam 中存储的是磁盘地址。）

再看一个范围查询的例子，假如我们想要查找9和26之间的数据。查找路径是磁盘块1 -> 磁盘块2 -> 磁盘块6 -> 磁盘块7。

  1. 首先查找值等于9的数据，将值等于9的数据缓存到结果集。这一步和前面等值查询流程一样，发生了三次磁盘 IO。
  2. 因为底层的叶子节点是一个双向有序链表，我们从磁盘块6，键值9开始向后遍历筛选所有符合筛选条件的数据。
  3. 第四次磁盘IO：根据磁盘块6后继指针到磁盘中寻址定位到磁盘块7，将磁盘块7加载到内存中，在内存中从头遍历比较，9<25<26，9<26<=26，将 data 缓存到结果集。
  4. 由于主键具备唯一性（后面不会有<=26的数据），所以不需再向后查找，查询终止。将结果集返回给用户。

结论：B+ 树更适合用来做存储索引

  • B+树的 I/O 次数最少，磁盘读写代价最低。（B树的节点是存放在内存页中的，而B+树的非叶子节点只存储值信息，不存储数据。那么在相同的内存页大小（一般为 4k）的情况下，B+树能够存储更多的键值，那么整体树结构的高度就会更小，需要的 I/O 次数也会更少）
  • B+树的查询效率稳定。（所有的数据都存储在叶子节点上，非叶子节点只存储索引。因此所有关键字查询的长度相同，时间复杂度为稳定的O(logn)）
  • B+树最有利于做区间检索和范围查询。（B+树在做范围查询时有更高的性能，其叶子节点都是连在一起的，只需一次范围查询即可）

    5.5 Hash 索引

    数据库索引 - 图3
    Hash 索引可以用 Key 存储索引列，用 Value 存储行记录或者行磁盘地址。Hash 索引在等值查询时效率很高，时间复杂度为O(1)。但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

虽然 Hash 索引的理论上的查询效率高，但是 Hash 索引也有很多缺点以及不稳定的地方：

  1. 仅仅只能满足 “=”，“IN”，不能使用范围查询
  2. 无法被用来避免数据的排序操作
  3. 不能利用部分索引键查询（B+ 树支持利用主合索引中的部分索引）
  4. 不能避免表扫描（多个 key 会指向同一个哈希地址，还是得访问 bucket 中的实际数据）
  5. 遇到大量 Hash 值相等的情况下，性能并不一定就会比 B+ Tree 索引高（此时可能存在大量数据存于同一个 bucket 中）

虽然 InnoDB 支持 Hash 索引，但是支持的哈希索引是自适应的，InnoDB 存储引擎会根据表的使用情况自动为表生成自适应哈希索引，当某个索引值被使用的非常频繁时，会在 B+ 树索引之上再创建一个哈希索引，这样就让 B+ 树索引具有哈希索引的一些优点，比如哈希的等值查询。

补充：MySQL 数据库不支持位图索引。

6. 聚簇索引和非聚簇索引的区别

先上定义：

  • 聚簇索引（主键索引）：聚簇索引的主键索引的叶子结点存储的是键值对应的数据本身；辅助索引的叶子结点存储的是键值对应的数据的主键键值。（InnoDB 的实现方式，将数据与索引一起存储，索引结构的叶子节点保存了行数据）
  • 非聚簇索引（二级索引）：非聚簇索引的主键索引和辅助索引几乎是一样的，只是主索引不允许重复，不允许空值，他们的叶子结点都存储指向键值对应的数据的物理地址。（MyISAM 的实现方式，将数据与索引分开存储，索引结构的叶子节点指向了数据对应的位置）

对比聚簇索引和非聚簇索引，可以发现二者最主要的区别就是在于是否在 B+Tree 的节点中存储数据，也就是数据和索引是否存储在一起。这个区别导致最大的问题就是聚簇索引的索引的顺序和数据本身的顺序是相同的，而非聚簇索引的顺序跟数据的顺序没有什么关系。

聚簇索引（InnoDB 的索引实现）

聚簇索引具有唯一性，表中行的物理顺序和索引中行的物理顺序是相同的，因此一个表仅有一个聚簇索引。辅助索引叶子节点存储的不再是行的物理位置，而是主键值，辅助索引访问数据总是需要二次查找。根据在辅助索引树中获取的主键id，到主键索引树检索数据的过程称为回表查询。
数据库索引 - 图4

  1. InnoDB 使用的是聚簇索引，将主键组织到一棵 B+ 树中，而行数据就存储在叶子节点上。在根据主键索引搜索数据时，如使用 where id = 14 这样的条件查找主键，则按照 B+ 树的检索算法即可查找到对应的叶节点，之后获得行数据。
  2. 而在根据辅助索引搜索数据时，如对 AGE 列进行条件检索，则需要两个步骤：第一步在辅助索引 B+ 树 中检索 AGE，到达其叶子节点获取对应的主键。第二步使用主键在主索引 B+ 树中再执行一次检索操作，最终到达叶子节点即可获取整行数据。

对于 InnoDB，必须有一个主键，且该主键作为唯一的聚簇索引。

  • 若已经有一个主键被定义，该主键则作为聚簇索引。
  • 若没有主键被定义，该表的第一个唯一非空索引则作为聚簇索引。
  • 若不满足以上条件，InnoDB 内部会生成一个隐藏主键作为聚簇索引。

    非聚簇索引（MYISAM 的索引实现）

    数据库索引 - 图5
    MyISAM 使用的是非聚簇索引，非聚簇索引的主键索引和辅助索引几乎是一样的，只是主索引不允许重复，不允许空值。

MyISAM 使用 B+树 构建索引树时，叶子节点中存储的键值为索引列的值，数据为索引所在行的磁盘地址。并且非聚簇索引将数据文件和索引文件分开存储。

7. 组合索引

以自己创建的一个表为例：表 abc_innodb，id为主键索引，创建了一个联合索引idx_abc(a,b,c)。

  1. CREATE TABLE `abc_innodb`  
  2. (  
  3.     `id` int(11) NOTNULL AUTO_INCREMENT,  
  4.     `a` int(11) DEFAULT NULL,  
  5.     `b`int(11)     DEFAULT NULL,  
  6.     `c`varchar(10) DEFAULT NULL,  
  7.     `d`varchar(10) DEFAULT NULL,  
  8.     PRIMARY KEY (`id`) USING BTREE,  
  9.     KEY `idx_abc` (`a`, `b`, `c`)  
  10. ) ENGINE = InnoDB;

数据库索引 - 图6
数据库索引 - 图7

7.1 最左匹配原则

组合索引的最左前缀匹配原则即：使用组合索引查询时，mysql会一直向右匹配直至遇到范围查询(>、<、between、like)就停止匹配。

之所以在组合索引中存在最左匹配原则，是因为最左前缀匹配原则和组合索引的索引存储结构和检索方式是有关系的。在组合索引树中，最底层的叶子节点按照第一列a列从左到右递增排列，但是b列和c列是无序的，b列只有在a列值相等的情况下小范围内递增有序，而c列只能在a，b两列相等的情况下小范围内递增有序。

在上图的例子中，联合索引会按照a列创建一个B+树，再按照b列进行排序。在查询时，B+树会先比较a列来确定下一步应该搜索的方向，往左还是往右。如果a列相同再比较b列。但是如果查询条件没有a列，B+树就不知道第一步应该从哪个节点查起。

可以说创建了idx_abc(a,b,c)索引之后，相当于创建了(a)、(a,b)、(a,b,c)三个索引。

  1. 最左前缀匹配原则是组合索引中非常重要的原则，MySQL 会一直向右匹配直到遇到范围查询（>、<、between、like）就停止匹配，比如 a=3 and b=4 and c>5 and d=6，如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
  2. = 和 in 可以乱序，比如a=1 and b=2 and c=3建立(a,b,c)索引可以任意顺序，MySQL 的查询优化器会帮你优化成索引可以识别的形式。

7.2 组合索引的创建原则

  1. 把频繁使用的列、区分度高的列放在前面，频繁使用代表索引利用率高，区分度高代表筛选粒度大。
  2. 将常需要作为查询返回的字段上增加到组合索引中，这样可以使用到覆盖索引。
  3. 考虑当前是否已经存在多个可以合并的单列索引，如果有，那么将当前多个单列索引创建为一个组合索引。

    8. 什么是覆盖索引?

    覆盖索引并不是一种索引结构，它是一种很常用的优化手段。因为在使用辅助索引的时候，我们只可以拿到主键值，相当于获取数据还需要再根据主键查询主键索引再获取到数据。但是试想下这么一种情况，在上面联合索引的abc_innodb表中的使用组合索引查询时，如果我只需要a、b、c三个字段，那是不是意味着我们查询到组合索引的叶子节点就可以直接返回了，而不需要回表。这种情况就是覆盖索引。

所以覆盖索引的定义就是在一次查询中，如果一个索引覆盖所有需要查询的字段的值，我们就称之为覆盖索引，而不再需要回表查询。

要确定一个查询是否是覆盖索引，我们只需要 explain sql 语句看Extra的结果是否是Using index即可。

9. 哪些场景会造成索引失效？

  1. 应尽量避免在 where 子句中使用 != 或 <> 操作符，否则引擎将放弃使用索引而进行全表扫描；
  2. 尽量避免在 where 子句中使用 or 来连接条件，否则将导致引擎放弃使用索引而进行全表扫描，即使其中有条件带索引也不会使用，这也是为什么尽量少用 or 的原因；
  3. 对于多列索引，不是使用的第一部分，则不会使用索引；
  4. 如果列类型是字符串，那一定要在条件中将数据使用引号引用起来，否则不会使用索引；
  5. like的模糊查询以 % 开头，索引失效；
  6. 应尽量避免在 where 子句中对字段进行表达式操作，这将导致引擎放弃使用索引而进行全表扫描；
  7. 应尽量避免在 where 子句中对字段进行函数操作，这将导致引擎放弃使用索引而进行全表扫描；
  8. 不要在 where 子句中的 “=” 左边进行函数、算术运算或其他表达式运算，否则系统将可能无法正确使用索引；
  9. 如果MySQL估计使用全表扫描要比使用索引快，则不使用索引；

  10. 不适合键值较少的列（重复数据较多的列）

    10. 建立索引应该遵循的原则

  11. 在经常需要搜索的列上建立索引，可以加快搜索的速度。

  12. 在作为主键的列上创建索引，强制该列的唯一性，并组织表中数据的排列结构。
  13. 在经常使用表连接的列上创建索引，这些列主要是一些外键，可以加快表连接的速度。
  14. 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，所以其指定的范围是连续的。
  15. 在经常需要排序的列上创建索引，因为索引已经排序，所以查询时可以利用索引的排序，加快排序查询。
  16. 在经常使用 WHERE 子句的列上创建6索引，加快条件的判断速度。

参考

  1. 一口气搞懂 MySQL 索引所有知识点