1. MySQL 有哪些索引类型？#
分析
索引都是由存储引擎来实现的，不同存储引擎支持的索引类型也是不同的。大多数存储引擎都支持 B+ 树索引，而哈希索引只有 Memory 引擎实现了。
B+ 树索引、哈希索引、全文索引的区别：
- B+ 树索引： B+ 树索引是一种平衡树数据结构，它将数据按照索引键值有序地存储在树的叶子节点上，非叶子节点只存储索引键值和指向下一层节点的指针，适合于范围查找、排序查询、等值查询，并且性能稳定。因为 B+ 树保存千万级别的数据，树的高度依然维持在 3～4 层左右，也就是从千万级数据查询一条数据只需要 3～4 次磁盘 I/O 操作就能查询到目标数据。
- 哈希索引： 哈希索引是通过哈希算法将键值（key-value）映射到哈希表中，再根据哈希表进行索引操作。哈希索引适合于等值查询，例如根据主键查询某条记录，查询时间复杂度为 \(O(1)\)，效率非常高，但不支持排序、范围查询及模糊查询等。
- 全文索引： 全文索引是一种用于全文搜索的索引技术，可以对文本内容进行索引，支持关键词的模糊匹配和搜索。一般用于查找文本中的关键字，而不是直接比较是否相等，主要是用来解决
WHERE name LIKE "%aaaa%"等针对文本的模糊查询效率低的问题。
回答
我了解到 MySQL 支持 B+ 树索引、哈希索引、全文索引这三种索引类型。我比较常用的是 B+ 树索引，因为它是 InnoDB 引擎默认使用的索引类型，支持排序、分组、范围查询、模糊查询等功能。
2. InnoDB 引擎的索引数据结构是什么？#
分析
InnoDB 存储引擎支持两种索引数据结构，B+ 树索引和 FULLTEXT 索引。面试的时候，说一个 B+ 树索引就行，如果对 FULLTEXT 索引了解不多，可以不说，容易被追问。
回答
我了解到 InnoDB 引擎采用了 B+ 树作为索引的数据结构。它的一些特性：
- 数据组织形式：InnoDB 存储引擎的主键索引 B+ 树的非叶子节点只存放索引键值和指向子节点的指针，不存储实际的数据，这里对应到 MySQL 中就是索引。叶子节点存储索引键值和行数据，所以 InnoDB 存储引擎的主键索引属于聚簇索引。
- 叶子节点链表：所有叶子节点通过指针相连，形成一个双向链表，支持快速的顺序访问和范围查询。
- 平衡树结构：所有叶子节点在同一层上，树的高度平衡，保证任何数据记录的查找、插入、删除和更新操作的路径长度相同，稳定性好。
3. B+ 树的特性是什么？#
分析
至少回答出 B+ 树这 2 个特点：
- 叶子节点会存储索引和数据，中间节点不会存储数据。
- 叶子节点之间用双向链表组织。
回答
B+ 树是一个多叉树，一个父节点可以有多个子节点，主要的特性有三个：
- B+ 树的中间节点不会存储数据，而只有叶子节点才会存储，中间节点只用于存储到叶子节点的路由信息（即索引），而且每个节点里的数据都是根据索引的值来顺序存放的。
- B+ 树的所有叶子节点之间会通过双向指针串联在一起，构成一个双向链表，可以方便扫表和范围查询。
- B+ 树查询性能稳定，因为所有叶子节点都在同一层，确保了所有数据项的检索都具有相同的 I/O 延迟。而且 B+ 树保存千万级别的数据，树的高度依然维持在 3～4 层左右，也就是从千万级数据查询一条数据只需要 3～4 次磁盘 I/O 操作就能查询到目标数据。
4. B+ 和 B 树有什么区别？#
分析
从三个角度来说明区别：
- 数据存储的区别。
- 范围查询的区别。
- 查询效率的区别。
回答
B+ 和 B 树都是多叉平衡树，每个节点包含多个键和多条链，主要的区别有这些：
- B 树所有节点都会存储索引和数据，而 B+ 树只有叶子节点才会存储数据，中间节点则只有索引。因此存储相同数据量的情况下，B+ 树可以比 B 树更矮胖，查询叶子节点的磁盘 I/O 次数会更少。
- B+ 树叶子节点之间会通过双向指针串联在一起，构成一个双向链表，这种设计对范围查找非常有帮助。而 B 树没有将所有叶子节点用链表串联起来的结构，只能通过中序遍历来完成范围查询，这会比 B+ 树范围查询涉及更多个节点的磁盘 I/O 操作，因此范围查询效率不如 B+ 树。
- B 树的优势是当要查找的值恰好处在一个非叶子节点时，由于该节点也包含数据，查找到该节点就会成功并结束查询，最快可以在 \(O(1)\) 的时间代价内查到。而 B+ 树由于数据只在叶子节点，所以每次查询都需要从根节点搜索到叶子节点。从平均时间代价来看，B 树会比 B+ 树稍快一些，但是 B+ 树的查询会更稳定，因为每次查询都是相同的 I/O 延迟。
5. MySQL 为什么使用 B+ 树？#
分析
这个面试官没有问 B+ 树和其他数据结构区别的时候，就需要自己主动去对比，比如平衡树、红黑树、跳表、B 树。
回答
- B+ 树是多叉树，而平衡二叉树、红黑树是二叉树。在同等数据量下，平衡二叉树、红黑树高度更高，磁盘 I/O 次数更多，性能更差，而且它们会频繁执行再平衡过程，来保证树形结构平衡。
- 跳表和 B+ 树相比，跳表在极端情况下会退化为链表，平衡性差，而数据库查询需要一个可预期的查询时间，并且跳表需要更多的内存。
- B 树和 B+ 树相比，B 树的数据存储在全部节点中，对范围查询不友好。非叶子节点存储了数据，导致内存中难以放下全部非叶子节点。如果内存放不下非叶子节点，那么查询非叶子节点的时候都需要磁盘 I/O。
6. 为什么索引用 B+ 树，而不用红黑树？#
分析
InnoDB 引擎的数据都是存储在磁盘上的，所以选择数据结构的第一优先级是考虑从磁盘查询数据的成本。如果树的高度越高，意味着磁盘 I/O 就越多，这样就会影响查询性能。
对于有 N 个叶子节点的 B+Tree，其搜索复杂度为 \(O(\log_d N)\)，其中 d 表示节点允许的最大子节点个数为 d 个。
在实际的应用当中，d 值是大于 100 的，这样就保证了，即使数据达到千万级别时，B+Tree 的高度依然维持在 3～4 层左右，也就是说一次数据查询操作只需要做 3～4 次的磁盘 I/O 操作就能查询到目标数据。
而红黑树本质上是二叉树，二叉树的每个父节点的儿子节点个数只能是 2 个，意味着其搜索复杂度为 \(O(\log N)\)，这已经比 B+Tree 高出不少，因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。
回答
我觉得主要原因是随着数据量的增多，红黑树的树高会比 B+ 树的树高高，这样查询数据的时候会面临更多的磁盘 I/O，查询性能没那么好。因为红黑树本质上是二叉树，而 B+ 树是多叉树，存储相同数量量的情况下，红黑树的树高会比 B+ 树的树高高。由于 InnoDB 引擎的数据都是存储在磁盘上的，如果树的高度越高，意味着磁盘 I/O 就越多，这样就会影响查询性能。
另外，B+ 树叶子节点是通过双向链表组织的，可以很好地实现范围查询，而红黑树要实现范围查询需要通过中序遍历，这会比 B+ 树范围查询涉及更多个节点的磁盘 I/O 操作，因此范围查询效率不如 B+ 树。
所以，B+ 树相比红黑树有两个优势：第一个优势是 B+ 树随着数据的增多的时候树的高度会比红黑树低，第二个优势是 B+ 树范围查询很方便，直接通过叶子节点的链表就能完成了，因此 InnoDB 存储引擎选择了 B+ 树作为索引。
7. 为什么索引用 B+ 树，而不用 B 树？#
分析
考察你对 B+ 树和 B 树的理解，可以从三个角度来分析，为什么索引不用 B 树：
- 磁盘 I/O 角度。
- 范围查询角度。
- 增删查改角度。
记不住三个也没关系，记住前 2 个原因也可以。
回答
我觉得主要有三个原因：
- B+ 树的磁盘读写代价更低：B+ 树只有叶子节点才会存放索引和数据，非叶节点只存放索引，而 B 树所有节点都会存放索引和数据。因此存储相同数据量的情况下，B+ 树可以比 B 树更矮胖，查询叶子节点的磁盘 I/O 次数会更少。
- B+ 树便于范围查询：MySQL 是需要经常使用范围查询的，B+ 树所有叶子节点间会用链表进行连接，这种设计对范围查找非常有帮助。而 B 树没有将所有叶子节点用链表串联起来的结构，只能通过中序遍历来完成范围查询，这会比 B+ 树范围查询涉及更多个节点的磁盘 I/O 操作，因此范围查询效率不如 B+ 树。
- B+ 树增删查改效率更加稳定：B+ 树有大量的冗余节点，这些冗余数据可以让 B+ 树在插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化。另外，B+ 树把所有的用户记录都放到了叶子节点这一层，因此查询、插入、删除数据都需要走到最后一层，这不同于 B 树可能在任意一层找到数据，所以 B+ 树更为稳定。
所以，InnoDB 引擎的索引选择了 B+ 树。
8. 为什么索引用 B+ 树，而不用哈希表？#
分析
- 哈希表的数据是散列分布的，不具备有序性，无法进行范围查询和排序。
- 哈希表存在哈希冲突的问题，哈希冲突严重，也会降低查询效率。
回答
MySQL 会有很多范围查询和排序的场景。虽然哈希表的搜索时间复杂度是 \(O(1)\)，但是由于哈希表的数据都是通过哈希函数计算后散列分布的，所以哈希表索引不支持范围查询和排序操作，不支持联合索引最左匹配原则。如果重复键值比较多，还容易造成哈希碰撞导致效率进一步降低。而 B+ 树可以满足这些应用场景，因此选择了用 B+ 树索引。
9. B+ 树有什么优点和缺点？#
分析
一问到 B+ 树的缺点，很多人就懵了，因为前面都在说 B+ 树的各种优点。
- B+ 树最大优点是 B+ 树的叶子节点形成了一个有序链表，可以方便地进行范围查询。相比较而言，B 树和二叉树需要在非叶子节点进行回溯才能找到所有满足条件的记录，这会增加额外的开销。
- B+ 树缺点是可能会产生大量的随机 I/O，每次修改数据都很有可能破坏 B+ 树的约束，我们需要对整棵树进行递归的合并、分裂等调整操作。而不同节点在磁盘上的位置很可能并不是连续的，这就导致我们需要不断地做随机写入的操作。
回答
- B+ 树有一个最大的好处是方便范围查询。B+ 树的叶子节点之间有链表，直接通过叶子节点链表就能方便地完成范围查询的工作，而 B 树必须用中序遍历的方法来实现范围查询，这会比 B+ 树范围查询涉及更多个节点的磁盘 I/O 操作，因此范围查询效率不如 B+ 树。
- B+ 树最大的性能问题是会产生大量的随机 I/O。随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离得很远。做范围查询时，会产生大量读随机 I/O。对于大量的随机写也一样，举一个插入 key 跨度很大的例子，如
7 -> 1000 -> 3 -> 2000，新插入的数据存储在磁盘上相隔很远，会产生大量的随机写 I/O。
10. 聚簇索引和非聚簇索引有什么区别？#
分析
先说聚簇索引和非聚簇索引 B+ 树叶子节点存放内容的区别，然后再引出回表查询和覆盖索引查询。
回答
聚簇索引和非聚簇索引（二级索引）最主要的区别是 B+ 树叶子节点存放的内容不同：
- 聚簇索引的 B+ 树叶子节点存放的是主键值和完整的记录。
- 非聚簇索引的 B+ 树叶子节点存放的是索引值和主键值。
如果查询语句的查询条件用了二级索引，但是查询的数据不是主键值，也不是二级索引值，这时在二级索引找到主键值后，就需要回表才能查找到数据；如果查询的列是主键值和二级索引值时，因为只在二级索引就能查询到，这时候就会用到覆盖索引，不需要回表，只需要扫描一次 B+ 树。
11. 什么是覆盖索引？#
分析
二级索引的叶子节点存放的是索引和主键 id，如果查询的列能够在二级索引中全部查询到，那就不需要回到主键索引去查行记录了，这种不需要回表的过程，就叫覆盖索引，效率会比较高。
假设有联合索引 (a, b)，当执行以下查询的时候，都会发生覆盖索引：
SELECT a, b, id FROM table WHERE a = ? AND b = ?;
SELECT a, b FROM table WHERE a = ? AND b = ?;
SELECT a, id FROM table WHERE a = ? AND b = ?;
SELECT b, id FROM table WHERE a = ? AND b = ?;
SELECT a FROM table WHERE a = ? AND b = ?;
SELECT b FROM table WHERE a = ? AND b = ?;
SELECT id FROM table WHERE a = ? AND b = ?;
我们也可以通过 EXPLAIN 命令来确认查询是否用到了覆盖索引。
可以看到 Extra 信息显示 Using index，就代表查询用到了覆盖索引，不涉及回表的过程。
回答
当查询的数据是能在二级索引的叶子节点里查询到的话，这时就不用再回主键索引查了，也就不需要回到主键索引去查行记录了。这种不需要回表的过程，就叫覆盖索引。这种查询方式效率会比较高，只需要查二级索引这一棵 B+ 树。
12. 什么情况下会回表？#
分析
在使用二级索引进行查询的时候，如果查询的列不能在二级索引中全部查询到，那么就需要回到主键索引去查完整的行记录了，这种二级索引通过主键索引进行再一次查询的操作叫作「回表」。
假设有 product 表，字段为 product_no（商品编码），设置为二级索引，那么这个二级索引的索引键值是 product_no，B+ 树会根据 product_no 索引键值的顺序来存储数据，那么二级索引的B+ 树如下图：
上图中，非叶子节点的索引键值是 product_no（图中红色部分），叶子节点存储的是索引键值（图中红色部分）和主键值 （图中绿色部分）。
如果我用 product_no 二级索引查询商品，如下查询语句：
SELECT * FROM product WHERE product_no = '0008';
我们用 EXPLAIN 命令来看这个语句的执行情况，可以看到 key 不是 NULL，而是 idx_product_no，说明查询走了二级索引。
查询过程是这样的，先从二级索引 B+ 树自顶向下逐层进行查找：
- 将
0008与根节点的索引（0003、0006、0009）比较，0008大于索引值0006，说明0008肯定不在叶子节点 2。因为索引值6是叶子节点 2 中最大的索引值，0008小于索引值0009，这表示小于0009的数据在地址指向的下一层节点中，根节点索引键0009的指针地址指向的是「叶子节点 3」，因此这里定位的是0008在「叶子节点 3」中。 - 在「叶子节点 3」中根据二分查找算法就能找到索引键值为
0008的数据，但是这时候只能查到主键值（id = 8），而无法查询到完整的行记录。因为二级索引并不会存储完整的行记录，所以需要额外再通过主键索引到主键索引中查询到对应的叶子节点，这时候才能获取完整的行记录，也就是说要查两个 B+ 树才能查到最终的结果。
这种二级索引通过主键索引进行再一次查询的操作叫作「回表」，你可以通过下图理解二级索引的查询过程。
回答
在使用二级索引进行查询的时候，如果查询的列不能在二级索引中全部查询到，那么就会发生回表的过程。先通过二级索引的值查到聚簇索引值（即主键 id），再通过聚簇索引的值定位行记录数据，需要扫描两次索引 B+ 树，它的性能较扫一遍索引树更低。
13. insert 操作对 B+ 树结构的改变是怎么样的？#
分析
要说出页分裂问题，以及指出主键 id 要是顺序递增，如果是随机值（比如 UUID），就可能会频繁出现页分裂的现象，会严重影响性能。
如果我们使用非自增主键，由于每次插入主键的索引值都是随机的，因此每次插入新的数据时，就可能会插入到现有数据页中间的某个位置，这将不得不移动其它数据来满足新数据的插入，甚至需要从一个页面复制数据到另外一个页面，我们通常将这种情况称为页分裂。页分裂还可能会造成大量的内存碎片，导致索引结构不紧凑，从而影响查询效率。
举个例子，假设某个数据页中的数据是 1、3、5、9，且数据页满了，现在准备插入一个数据 7，则需要把数据页分割为两个数据页：
出现页分裂时，需要将一个页的记录移动到另外一个页，性能会受到影响，同时页空间的利用率下降，造成存储空间的浪费。
而如果记录是顺序插入的，例如插入数据 11，则只需开辟新的数据页，也就不会发生页分裂：
回答
B+ 树的数据都是有序的，所以：
- 如果我们使用主键是顺序递增，那么每次插入的新数据就会顺序插入到叶子节点最右边的节点里。如果该页满了，就会自动开辟一个新页面，将新数据插入到新页面。因为每次插入一条新记录，都是追加操作，不需要重新移动数据，因此这种插入数据的方法效率非常高。
- 如果我们使用主键不是顺序递增，由于每次插入主键的索引值都是随机的，因此每次插入新的数据时，就可能会插入到现有数据页中间的某个位置。为了保证 B+ 树的有序性，要移动其它数据来满足新数据的插入。如果该页面满了，就发生页分裂，这时候要从一个页面复制数据到另外一个页面，目的是保证后一个数据页中的所有主键值比前一个数据页中主键值大。页分裂可能会造成大量的内存碎片，导致索引结构不紧凑，从而影响查询效率。
所以，我们在设计主键的时候，最好采用自增的方式，或者顺序递增主键值。
14. 假如一张表有两千万的数据，B+ 树的高度是多少？怎么算的？#
分析
假设：
- 非叶子节点内指向其他页的数量为
x。 - 叶子节点内能容纳的数据行数为
y。 - B+ 树的层数为
z。
表总数会等于 x 的 z - 1 次方与 y 的乘积：
回答
具体要看数据库表的字段多不多，以及字段类型。假设一行记录是 1KB 大小，那么 2000 万的数据表，B+ 树大概是三层高度。
MySQL 数据页的大小是 16KB，去掉一些头信息，大概有 15KB 可以存储数据。
- 在索引页中主要记录的是主键与页号，假设主键
id类型是bigint，那就是 8 字节，页号固定为 4 字节，那么索引页中的一条数据也就是 12 byte。那么一个索引页可以存储15 * 1024 / 12 ≈ 1280个页号。 - 叶子节点中存放的是真正的行数据，这个影响的因素就会多很多，比如字段的类型、字段的数量。每行数据占用空间越大，页中所放的行数就会越少。假设按一条行数据 1KB 来算，那么一页就能存下 15 条，
15KB / 1KB = 15。
根据公式 Total = x^(z-1) * y，已知 x = 1280，y = 15，假设 B+ 树是三层，那么就是 z = 3，Total = 1280^2 * 15 = 24576000，约 2.45kw。所以一张 2000 万数据的表，B+ 树高度大概是 3 层。