02-MySQL 索引

官网保平安：https://www.mysql.com/
MySQL 思维导图：https://www.processon.com/view/link/63bc2c8ea82ed9463ba99f38

数据库底层实现

索引是排好序的数据结构。

hash 索引和 B+Tree 索引的区别 ★★★

  • hash 索引：hash 索引底层就是 hash 表，进行查找时，调用一次 hash 函数就可以获取到相应的键值，之后进行回表查询获得实际数据。

  • B+Tree 索引：B+Tree 底层实现是多路平衡查找树。对于每一次的查询都是从根节点出发，查找到叶子节点就可以获得所查键值，然后根据查询判断是否需要回表查询数据。

hash 索引和 B+Tree 索引的区别：

  1. hash 索引无法进行范围查询，因为是直接用 hash 函数定位到主键 id；而 B+Tree 因为维护了主键顺序（树结构的天然优势+非叶子结点按页存储主键值+叶子结点链表相连），所以可以进行范围查询。

  2. hash 索引不支持使用索引进行排序，原理同上。

  3. hash 索引不支持模糊查询以及多列索引的最左前缀匹配。原理也是因为 hash 函数的不可预测性。

  4. hash 索引任何时候都避免不了回表查询数据，而 B+Tree 索引在符合某些条件(聚簇索引，覆盖索引等)的时候可以只通过索引完成查询。

  5. hash 索引虽然在等值查询上较快，但是不稳定。性能不可预测，当某个键值存在大量重复的时候，发生 hash 碰撞，此时效率可能极差。而 B+Tree 索引的查询效率比较稳定，对于所有的查询都是从根节点到叶子节点，且树的高度较低。

红黑树、B-Tree 和 B+Tree 的区别

  • 红黑树：
    特点：左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    问题：尽量不让一棵树的单边变得太长而退化成链表，能有效地减少高度，高度变小降低了查找 I/O 的次数，性能比二叉树要好。但红黑树一个节点只能有两个子节点，虽然平衡了链表退化问题，但高度总体来看还是太高。

  • B-Tree：
    特点：每个节点都会存储索引和数据。每个非叶子节点有多个子节点。
    问题：B-Tree 在每一个节点存储了索引和数据，导致进行搜索的时候需要把索引和数据都加载到内存中，这样就不是很划算，内存资源这么宝贵，多存些索引岂不是更好。

  • B+Tree：
    特点：

    1. 非叶子节点不存储数据，只存索引（冗余），这样可以保证存放更多的索引。
    2. 叶子节点存储所有索引字段。
    3. 叶子节点用指针连接，提高区间访问性能。

MySQL 数据库索引是使用什么数据结构实现的，有什么优点

  1. 内部节点只保存引，不保存实际的数据，所以非叶子节点可以保存更多的索引，所以比 B+Tree 的层数低，这样 IO 读写次数就降低了，加快查找时间。
  2. 叶子节点中包含所有数据，所有叶子节点形成一个有序链表，让范围查找更高效。
  3. B+Tree 查询效率稳定，任何关键字的查找必须要走一条根节点到叶子节点的路，所有关键字的查询路径长度相当，导致每一个数据的查询效率相当。

InnoDB 索引的原理 ★★★

为什么选择 B+Tree：

  • 哈希索引虽然能提供 O(1) 复杂度查询，但对范围查询和排序却无法很好的支持，最终会导致全表扫描。
  • B-Tree 能够在非叶子节点存储数据，但会导致在查询连续数据时可能带来更多的随机 IO。
  • B+Tree 的非叶子节点只存储索引，会大大节省存储空间，提高单页存储索引的数量，减少树的层级，也就减少了 IO。
    B+Tree 中所有的数据都存储在叶子节点上，所有叶节点通过指针来相互连接，减少顺序遍历和范围遍历带来的随机 IO。

为什么 B+Tree 有优势，底层原因是什么：

  • B+Tree 适合作为数据库的基础结构，完全是因为计算机的 内存-机械硬盘 两层存储结构。内存可以完成快速的随机访问，但是容量较小，而硬盘的随机访问要经过机械动作（1磁头移动，2盘片转动），访问效率比内存低几个数量级，但是硬盘容量较大。所以叶子节点只存索引的话，可以大大增加每次从硬盘读取的数据。
  • 考虑到磁盘 IO 是非常高昂的操作，计算机操作系统做了一些优化：当进行一次 IO 时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。
    每一次 IO 读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为 4k 或 8k，也就是我们读取一页内的数据时候，实际上才发生了一次 IO，这个理论对于索引的数据结构设计非常有帮助。
    一页就是一个磁盘块(block块)，InnoDB 一页 16k，即一次 IO 读 16k 到内存中。

总结：其实是两个考虑因素：

  • InnoDB 需要执行的场景和功能需要在特定查询上拥有较强的性能。
  • CPU 将磁盘上的数据加载到内存中需要花费大量时间。

真实数据库中的 B+Tree 应该是非常扁平的。所以如果是聚簇索引的话，每次只需要 3 到 4 次磁盘 IO 操作。举例如下：

  1. 一个 bigint 类型的索引占用 8B，索引对应的子树的指针占用 6B，所以 InnoDB 一页大概可以存放 16k/(6B+8B)=1170 个索引。
  2. 如果 B+Tree 的高度为 3，则一共可以放 1170*1170 个索引。
  3. 如果每条数据占用 1k，那么一页可以放 16 条数据。 那么高度为 3 的 B+Tree 可以放 1170*1170*16 大约 2100 万条数据。

看下如何定位一个 Record：

  1. 通过根节点开始遍历一个索引的 B+Tree，通过各层非叶子节点最终到达一个 Page，这个 Page 里存放的都是叶子节点。
  2. 在 Page 内从 “Infimum” 节点开始遍历单链表（这种遍历往往会被优化），如果找到该键则成功返回。如果记录到达了”supremum”，说明当前 Page 里没有合适的键，这时要借助 Page 的 Next Page 指针，跳转到下一个 Page 继续从”Infimum”开始逐个查找。

MyISAM 和 InnoDB 实现 B+Tree 索引方式的区别是什么 ★★★

  • MyISAM：B+Tree 索引的叶子节点保存数据的物理地址，叶节点的 data 域存放的是数据记录的地址，索引文件和数据文件是分离的。MyISAM 的辅助索引 data 域存储相应记录的地址。
  • InnoDB：B+Tree 索引的叶子节点保存数据本身，其数据文件本身就是索引文件。InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。

B+Tree 做索引这么好，为什么有些非关系型数据库使用 B-Tree 做索引呢

虽然遍历数据的查询是相对常见的，但是 MongoDB 认为查询单个数据记录远比遍历数据更加常见，由于 B-Tree 的非叶结点也可以存储数据，所以查询一条数据所需要的平均随机 IO 次数会比 B+Tree 少，使用 B-Tree 的 MongoDB 在类似场景中的查询速度就会比 MySQL 快。

这里并不是说 MongoDB 并不能对数据进行遍历，我们在 MongoDB 中也可以使用范围来查询一批满足对应条件的记录，只是需要的时间会比 MySQL 长一些。

那为什么不使用哈希作为底层的数据结构呢？

如果我们使用哈希，那么对于所有单条记录查询的复杂度都会是 O(1)，但是遍历数据的复杂度就是 O(n)；这不能满足 MongoDB 面对的场景：单记录查询非常常见，但是对于遍历数据也需要有相对较好的性能支持，哈希这种性能表现较为极端的数据结构往往只能在简单、极端的场景下使用。

InnoDB 支持 hash 索引吗

InnoDB 是支持 hash 索引的，不过其支持的 hash 索引是自适应的，InnoDB 会根据表的使用情况自动为表生成 hash 索引，不能人为干预是否在一张表中生成 hash 索引。

InnoDB 主键索引的叶节点含完整的数据记录，那主键索引文件要比数据文件大吗

  1. 在 Innodb 引擎中，主键索引中的叶子结点包含记录数据，主键索引文件即为数据文件。
  2. 在 tables 表中统计的 data_length 数据为主键索引大小，index_length 为统计的这个表中所有辅助索引（二级索引）索引的大小。

请尽量在 InnoDB 上采用自增字段做表的主键。因为 InnoDB 数据文件本身是一棵 B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree 的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。

唯一索引比普通索引快吗, 为什么

唯一索引不一定比普通索引快, 还可能慢。

  1. 查询时，在未使用 limit 1 的情况下，在匹配到一条数据后，唯一索引即返回，普通索引会继续匹配下一条数据，发现不匹配后返回，如此看来唯一索引少了一次匹配，但实际上这个消耗微乎其微。

  2. 更新时，这个情况就比较复杂了。普通索引将记录放到 change buffer 中语句就执行完毕了。而对唯一索引而言，它必须要校验唯一性，因此必须将数据页读入内存确定没有冲突，然后才能继续操作。

对于写多读少的情况, 普通索引利用 change buffer 有效减少了对磁盘的访问次数, 因此普通索引性能要高于唯一索引。

在对 name 做了唯一索引前提下，简述以下区别：

1
2
select * from tb where name = '小明'
select * from tb where name = '小明' limit 1
  • 没做唯一索引：前者查询会全表扫描，效率低些；limit 1，只要找到对应一条数据，就不继续往下扫描。
  • name 字段添加唯一索引：加不加 limit 1，意义都不大。

索引和约束

详细请参考：https://blog.csdn.net/fenglepeng/article/details/103141756

数据库五大约束

  • PRIMARY KEY: 设置主键约束。
  • UNIQUE: 设置唯一性约束，不能有重复值。
  • DEFAULT: 默认值约束。
  • NOT NULL: 设置非空约束，该字段不能为空。
  • FOREIGN key: 设置外键约束。

MySQL索引种类 ★★★

  • 普通索引：仅加速查询。
  • 唯一索引：加速查询 + 列值唯一（可以有null）。
  • 主键索引：加速查询 + 列值唯一 + 表中只有一个（不可以有null）。
  • 组合索引：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并。
  • 全文索引：对文本的内容进行分词，进行搜索。目前只有 CHAR、VARCHAR ，TEXT 列上可以创建全文索引。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替。

MySQL 8.x 中实现的索引新特性：

  • 隐藏索引：也称为不可见索引，不会被优化器使用，但是仍然需要维护，通常会软删除和灰度发布的场景中使用。主键不能设置为隐藏（包括显式设置或隐式设置）。
  • 降序索引：之前的版本就支持通过 desc 来指定索引为降序，但实际上创建的仍然是常规的升序索引。直到 MySQL 8.x 版本才开始真正支持降序索引。另外，在 MySQL 8.x 版本中，不再对 GROUP BY 语句进行隐式排序。
  • 函数索引：从 MySQL 8.0.13 版本开始支持在索引中使用函数或者表达式的值，也就是在索引中可以包含函数或者表达式。

再来一种分类，这两种索引不是创建的索引类型，是 SQL 执行时的采用的类型:

  1. 索引合并：利用多个单列索引查询。

    • 索引合并访问方法可以在查询中对一个表使用多个索引，对它们同时扫描，并且合并结果。
    • 合并只能合并单个表的索引，它不能合并多个表的扫描。

  2. 索引覆盖：在索引表中就能将想要的数据查询到。
    就是 select 的数据列只用从索引中就能够取得，不必从数据表中读取，换句话说查询列被所使用的索引覆盖。
    索引是高效找到行的一个方法，当能通过检索索引就可以读取想要的数据，那就不需要再到数据表中读取行了。
    注意：MySQL 只能使用 B+Tree 索引做覆盖索引。

B+Tree 索引中的聚集索引与辅助索引

  • InnoDB 存储引擎表是索引组织表，即表中数据按照主键顺序存放。聚集索引就是按照每张表的主键构造一棵 B+Tree，同时叶子结点存放的即为整张表的行记录数据，也将聚集索引的叶子结点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同 B+ 树数据结构一样，每个数据页都通过一个双向链表来进行链接。
  • 除了聚集索引外其他索引都是辅助索引（也称为非聚集索引），与聚集索引的区别是：辅助索引的叶子节点不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含一个书签（bookmark）。该书签用来告诉 InnoDB 存储引擎去哪里可以找到与索引相对应的行数据。

什么是回表 ★★★

回表，顾名思义就是回到表中，也就是先通过普通索引扫描出数据所在的行，再通过行 主键ID 取出索引中未包含的数据。所以回表的产生也是需要一定条件的，如果一次索引查询就能获得所有的 select 记录就不需要回表，如果 select 所需的列中有非索引列，就会发生回表动作。即基于非主键索引的查询需要多扫描一棵索引树。

MyISAM 没有回表。

索引在什么情况下遵循最左前缀的规则 ★★★

当 b+Tree 的数据项是复合的数据结构，比如 (name,age,sex) 的时候，b+Tree 是按照从左到右的顺序来建立搜索树的，有以下几种情况：

  • 等值查询：

    • 当 (张三,20,F) 这样的数据来检索的时候，B+Tree 会优先比较 name 来确定下一步的所搜方向，如果 name 相同再依次比较 age 和 sex，最后得到检索的数据。

    • 当 (20,F,张三) 这样的数据来检索的时候，B+Tree 会优化这个查询，把他变为 (张三,20,F)。

    • 当 (20,F) 这样的没有 name 的数据来的时候，B+Tree 就不知道下一步该查哪个节点，因为建立搜索树的时候 name 就是第一个比较因子，必须要先根据 name 来搜索才能知道下一步去哪里查询。

    • 当 (张三,F) 这样的数据来检索时，B+Tree 可以用 name 来指定搜索方向。

      • MySQL5.6 之前：下一个字段 age 的缺失，所以只能把名字等于张三的数据都找到，然后再回表取数据，再匹配性别是F的数据。
      • MySQL5.6 之后：MySQL 新增了索引下推的功能，直接使用组合索引判断符合查询条件的数据，然后再回表取数据，有效减少了回表的次数。

  • 范围查询

    • 当 (in(张三,李四,...), >20, in(F,M) 这样的数据来检索的时候：
      • 如果条件是 AND，则对顺序没有要求，因为 MySQL 会优化这个查询
      • 如果条件是 OR，有可能会用到 张三 的索引，如果 MySQL 觉得使用索引的效率不如 全排序，则会放弃索引。

  • 特殊情况

    • 如果查询出现索引覆盖，那么对于 (20,F) 这样的查询也可以用到索引。这个是 MySQL 优化器的特性。

列举创建索引但是无法命中索引的情况 ★★★

  • is null 可以用到索引，is not null不能用到索引。
  • 范围问题，或者说条件不明确，条件中出现这些符号或关键字：>、>=、<、<=、!= 、between...and...、like。
    • 范围查询在范围较小时可以用到索引，但是当范围很大时，速度小于全表扫描时，利用不到索引。
    • like 的 % 在最前面时用不到，如like '%xx' 。
  • 使用函数。
    • select * from tb1 where reverse(name)='zgc';
  • 索引列在条件中参与计算。
    • select * from tb1 where age+1=2
  • 类型不一致，如果列是字符串类型，传入条件是必须用引号引起来，不然则可能会无法命中。
    • select * from tb1 where name=666
  • 排序条件为索引，则 select 字段必须也是索引字段，否则无法命中。
    • select name from s1 order by email desc;
  • 使用 or, 当条件中有未建立索引的列时失效。
    • select * from tb1 where nid=1 or email='zgc@gmial.com'; nid 或者 email 未同时建立索引，或者建立的是组合索引（nid，email），这两种情况都会失效。
  • 组合索引最左前缀, 如果组合索引为，见上文。

1000w 条数据，使用 limit offset 分页时，为什么越往后翻越慢？如何解决？ ★★★

例如: limit 100000,20; = limit 20 offset 100000; 两个语句都是说从第十万条开始往后取二十条，因为这两条语句执行时是先扫描前 10w 行，然后从 10W 条数据开始读 20 条。

最简单：可以按照当前业务需求，看是否可以设置只允许看前 200 页，一般情况下，没人会咔咔看个几十上百页。

范围查询

当可以保证 ID 的连续性时，根据 ID 范围进行分页是比较好的解决方案：

1
2
3
4
# 查询指定 ID 范围的数据
SELECT * FROM t_order WHERE id > 100000 AND id <= 100010 ORDER BY id
# 也可以通过记录上次查询结果的最后一条记录的ID进行下一页的查询：
SELECT * FROM t_order WHERE id > 100000 LIMIT 10

这种优化方式限制比较大，且一般项目的 ID 也没办法保证完全连续。

子查询

我们先查询出 limit 第一个参数对应的主键值，再根据这个主键值再去过滤并 limit，这样效率会更快一些。

1
2
# 通过子查询来获取 id 的起始值，把 limit 1000000 的条件转移到子查询
SELECT * FROM t_order WHERE id >= (SELECT id FROM t_order limit 1000000, 1) LIMIT 10;

不过，子查询的结果会产生一张新表，会影响性能，应该尽量避免大量使用子查询。并且，这种方法只适用于 ID 是正序的。在复杂分页场景，往往需要通过过滤条件，筛选到符合条件的 ID，此时的 ID 是离散且不连续的。

当然，我们也可以利用子查询先去获取目标分页的 ID 集合，然后再根据 ID 集合获取内容，但这种写法非常繁琐，不如使用 INNER JOIN 延迟关联。

延迟关联

延迟关联的优化思路，跟子查询的优化思路其实是一样的：都是把条件转移到主键索引树，减少回表的次数。不同点是，延迟关联使用了 INNER JOIN（内连接） 包含子查询。

阿里巴巴《Java 开发手册》中也有对应的描述：

利用延迟关联或者子查询优化超多分页场景。

1
2
3
SELECT t1.* FROM t_order t1
INNER JOIN (SELECT id FROM t_order limit 1000000, 10) t2
ON t1.id = t2.id;

除了使用 INNER JOIN 之外，还可以使用逗号连接子查询。

1
2
3
SELECT t1.* FROM t_order t1,
(SELECT id FROM t_order limit 1000000, 10) t2
WHERE t1.id = t2.id;

覆盖索引

索引中已经包含了所有需要获取的字段的查询方式称为覆盖索引。

覆盖索引的好处：

  • 避免 InnoDB 表进行索引的二次查询，也就是回表操作: InnoDB 是以聚集索引的顺序来存储的，对于 InnoDB 来说，二级索引在叶子节点中所保存的是行的主键信息，如果是用二级索引查询数据的话，在查找到相应的键值后，还要通过主键进行二次查询才能获取我们真实所需要的数据。而在覆盖索引中，二级索引的键值中可以获取所有的数据，避免了对主键的二次查询（回表），减少了 IO 操作，提升了查询效率。
  • 可以把随机 IO 变成顺序 IO 加快查询效率: 由于覆盖索引是按键值的顺序存储的，对于 IO 密集型的范围查找来说，对比随机从磁盘读取每一行的数据 IO 要少的多，因此利用覆盖索引在访问时也可以把磁盘的随机读取的 IO 转变成索引查找的顺序 IO。
1
2
3
4
# 如果只需要查询 id, code, type 这三列，可建立 code 和 type 的覆盖索引
SELECT id, code, type FROM t_order
ORDER BY code
LIMIT 1000000, 10;

不过，当查询的结果集占表的总行数的很大一部分时，可能就不会走索引了，自动转换为全表扫描。当然了，也可以通过 FORCE INDEX 来强制查询优化器走索引，但这种提升效果一般不明显。

怎么查询表的所有索引

1
2
SHOW INDEX FROM ...
SHOW CREATE TABLE ...

可以使用多少列创建联合索引

任何标准表最多可以运行 16 个列创建联合索引。

索引的目的是什么

快速访问数据表中的特定信息，提高检索速度。

创建唯一性索引，保证数据库表中每一行数据的唯一性，加速表和表之间的连接。

使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。

索引对数据库系统的负面影响是什么

  • 创建索引和维护索引需要耗费时间，这个时间随着数据量的增加而增加。
  • 索引需要占用物理空间，不光是表需要占用数据空间，每个索引也需要占用物理空间。
  • 当对表进行增、删、改、的时候索引也要动态维护，这样就降低了数据的维护速度。

表中字段建立索引应该遵循几个原则 ★★★★★

  • 越小的数据类型通常更好：越小的数据类型通常在磁盘、内存中都需要更少的空间，处理起来更快。

  • 简单的数据类型更好：整型数据比起字符，处理开销更小，因为字符串的比较更复杂，处理起来也更耗时。

  • 尽量避免NULL：应该指定列为 NOT NULL。含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。你应该用0、一个特殊的值或者一个空串代替空值。

  • 使用区分度高的字段：对非唯一的字段，例如“性别”这种大量重复值的字段，增加索引也没有什么意义，所以索引的建立应当更多的选取唯一性更高的字段。

  • 联合索引遵循最左前缀(从最左侧开始检索)。

  • 不要创建太多索引：单个表上的索引个数不能超过 5 个，若太多则应考虑一些不常使用到的列上建的索引是否有必要。

  • 索引列的选择：

    • 频繁使用的列。
    • 出现在 SELECT、UPDATE、DELETE 语句的 WHERE 从句中的列。
    • 包含在 ORDER BY、GROUP BY、DISTINCT 中的字段。
    • 并不要将符合 1 和 2 中的字段的列都建立一个索引， 通常将 1、2 中的字段建立联合索引效果更好。
    • 多表 join 的关联列。这样，MySQL 内部会启动为你优化 Join 的 SQL 语句的机制。而且，这些被用来 Join 的字段，应该是相同的类型的。例如：如果你要把 DECIMAL 字段和一个 INT 字段 Join 在一起，MySQL 就无法使用它们的索引。对于那些 STRING 类型，还需要有相同的字符集才行。（两个表的字符集有可能不一样）。

  • 不必建索引的情况

    • where 条件中用不到的字段不适合建立索引。
    • 表记录较少。比如只有几百条数据，没必要加索引。
    • 需要经常增删改。需要评估是否适合加索引。
    • 参与列计算的列不适合建索引。
    • 区分度不高的字段不适合建立索引，如性别，只有男/女/未知三个值。加了索引，查询效率也不会提高。

为什么建议 InnoDB 表必须建主键，并且推荐使用整形的自增主键

在 InnoDB 的数据存储 idb 文件中，使用一个 B+Tree 保存数据，那么 MySQL 在组织索引的时候，会依赖唯一 id，有下列几种情况：

  • 如果有一个主键，可以直接使用主键建索引。
  • 如果没有主键，会从第一列开始选择一列所有值都不相同的，作为索引列。
  • 如果没有选到唯一值的索引列，MySQL 会帮忙建立一个隐藏列，维护一个唯一id，以此来组织索引。

反正都要建，为了避免 MySQL 选择索引列和建立隐藏列的性能损耗，建议手动建立一个主键。

为什么推荐使用整形作为主键

  • 使用整形作为主键相比字符型可以节省数据页的空间。
  • 构建索引 B+Tree 时，为了保证索引的有序性，使用整形可以避免页分裂。
  • 在索引中查找数据时，减少比较的性能。

主键为什么要自增

因为索引结构 b+Tree，具有有序的特性，如果主键不是自增的，在进行增删数据的时候，会判断数据应该存放的位置，进行插入和删除，为了保持平衡，会对数据页进行分裂等操作移动数据，严重影响性能，所以主键需要是自增的，插入时，插入在索引数据页最后。

#MySQL #面试
02-MySQL 索引
https://flepeng.github.io/interview-41-数据库-41-MySQL-02-MySQL-索引/
作者
Lepeng
发布于
2020年8月8日
许可协议