25Mysql面经补充

B+树、B树和红黑树的全称如下：

1. B树：
   • 全称：Balance-tree（平衡多路查找树）
   • 英文：B-tree
   • 说明：B代表”Balance”（平衡），表示这种树能保持数据有序且高度平衡。B树是为磁盘存储系统设计的自平衡多路查找树。
2. B+树：
   • 全称：B-plus tree（B树的改进版）
   • 英文：B+-tree
   • 说明：B+树是B树的一种变形，主要特点是”索引-数据分离”，即非叶子节点只存储索引，叶子节点存储数据并按顺序链接，特别适合数据库索引。
3. 红黑树：

   • 全称：Red-Black Tree（红黑树）

   • 英文：Red-Black Tree

   • 说明：红黑树是自平衡二叉查找树，每个节点有红色或黑色属性，通过颜色规则保持树的平衡。

   • 3层B+树可以存多少数据？

     进入正题，前面说了，3层B+树大概可以存2000w条数据，这个是咋算出来的呢？

     在Innodb存储引擎里面，咱们最小存储单元是页，而一个页的大小默认是16KB。

     也即代表B+树的每个节点可以存16KB数据，这里我们假设我们的一行数据大小是1K，那么我们一个节点就可以存16行数据。注意：我们真正的数据都是存在叶子节点的，所以这里是指叶子节点可以存放16行数据。

     我们前面也说了，非叶子节点存放的是主键值与指针，所以这里假设主键类型为bigint，占用8Byte，指针可以设置为占用6Byte，总共就为14Byte，这样就可以算出一个节点大概可以存放多少个指针了（指针指向下一层节点），大概为16KB/14Byte=1170个。

     由此，可以推算出，2层B+树的话，可以存放117016=18720行数据。3层B+树的话，可以存放11701170*16=21902400行数据，也就差不多2000w条数据了。

失效情况

最左前缀原则是MySQL在使用联合索引（复合索引）时的重要优化规则，要求查询条件必须从索引的最左列开始，并且连续匹配，才能高效利用索引。其底层依赖B+树的有序性：索引树首先按第一个字段排序，在此基础上再对第二个字段排序，依此类推

覆盖索引解决深分页问题

ICP

class Solution {
    List<String> ans = new ArrayList<>();

    void find(String s, String ip, int n) {
        if (n > 4) {
            return;
        } else if (n == 4) {
            if (s.isEmpty()) {
                ans.add(ip);
            }
            return;
        } else if (n > 0) {
            ip += ".";
        }

        for (int i = 1; i <= Math.min(s.length(), 4); i++) {
            String u = s.substring(0, i);
            // 判断数字范围
            if (Integer.parseInt(u) > 255) continue;
            // 判断前导零
            if (i > 1 && u.charAt(0) == '0') continue;
            find(s.substring(i), ip + u, n + 1);
        }
    }
    
    public List<String> restoreIpAddresses(String s) {
        find(s, "", 0);
        return ans;
    }
}

查询期间干了什么

执行一条 SQL 查询语句，期间发生了什么？

• 连接器：建立连接，管理连接、校验用户身份；
• 查询缓存：查询语句如果命中查询缓存则直接返回，否则继续往下执行。MySQL 8.0 已删除该模块；
• 解析 SQL，通过解析器对 SQL 查询语句进行词法分析、语法分析，然后构建语法树，方便后续模块读取表名、字段、语句类型；
• 执行 SQL：执行 SQL 共有三个阶段：
  • 预处理阶段：检查表或字段是否存在；将 select * 中的 * 符号扩展为表上的所有列。
  • 优化阶段：基于查询成本的考虑， 选择查询成本最小的执行计划；
  • 执行阶段：根据执行计划执行 SQL 查询语句，从存储引擎读取记录，返回给客户端；

索引的定义就是帮助存储引擎快速获取数据的一种数据结构，形象的说就是索引是数据的目录。

• 按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。
• 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。
• 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。
• 按「字段个数」分类：单列索引、联合索引。

>=能用到后续的索引

Q1: select * from t_table where a > 1 and b = 2，联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

但是在符合 a > 1 条件的二级索引记录的范围里，b 字段的值是无序的。

因此，Q1 这条查询语句只有 a 字段用到了联合索引进行索引查询，而 b 字段并没有使用到联合索引。

Q2: select * from t_table where a >= 1 and b = 2，联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

虽然在符合 a>= 1 条件的二级索引记录的范围里，b 字段的值是「无序」的，但是对于符合 a = 1 的二级索引记录的范围里，b 字段的值是「有序」的

所以，Q2 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。

Q3: SELECT * FROM t_table WHERE a BETWEEN 2 AND 8 AND b = 2，联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

Q3 查询条件中 a BETWEEN 2 AND 8 的意思是查询 a 字段的值在 2 和 8 之间的记录。不同的数据库对 BETWEEN … AND 处理方式是有差异的。在 MySQL 中，BETWEEN 包含了 value1 和 value2 边界值，类似于 >= and =<。而有的数据库则不包含 value1 和 value2 边界值（类似于 > and <）。

这里我们只讨论 MySQL。由于 MySQL 的 BETWEEN 包含 value1 和 value2 边界值，所以类似于 Q2 查询语句，因此 Q3 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。

综上所示，联合索引的最左匹配原则，在遇到范围查询（如 >、<）的时候，就会停止匹配，也就是范围查询的字段可以用到联合索引，但是在范围查询字段的后面的字段无法用到联合索引。注意，对于 >=、<=、BETWEEN、like 前缀匹配的范围查询，并不会停止匹配，前面我也用了四个例子说明了。

什么时候需要 / 不需要创建索引？

索引最大的好处是提高查询速度，但是索引也是有缺点的，比如：

• 需要占用物理空间，数量越大，占用空间越大；
• 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增大；
• 会降低表的增删改的效率，因为每次增删改索引，B+ 树为了维护索引有序性，都需要进行动态维护

为了更好的利用索引，索引列要设置为 NOT NULL 约束。有两个原因：

• 第一原因：索引列存在 NULL 就会导致优化器在做索引选择的时候更加复杂，更加难以优化，因为可为 NULL 的列会使索引、索引统计和值比较都更复杂，比如进行索引统计时，count 会省略值为NULL 的行。
• 第二个原因：行格式 (opens new window)](https://xiaolincoding.com/mysql/base/row_format.html#innodb-行格式有哪些)中**至少会用 1 字节空间存储 NULL 值列表**，如下图的紫色部分

深度分页（走索引，业务解决）

事务

事务 是指在数据库中执行的一事务看起来感觉简单，但是要实现事务必须要遵守 4 个特性，分别如下：

• 原子性（Atomicity）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节
• 一致性（Consistency）：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态。比如，用户 A 和用户 B 在银行分别有 800 元和 600 元，总共 1400 元，
• 隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致
• 持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

InnoDB 引擎通过什么技术来保证事务的这四个特性的呢？

• 持久性是通过 redo log （重做日志）来保证的；
• 原子性是通过 undo log（回滚日志） 来保证的；
• 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
• 一致性则是通过持久性+原子性+隔离性来保证；

mvcc的意思是多版本并发控制。指维护一个数据的多个版本，使得读写操作没有冲突，它的底层实现主要是分为了三个部分，第一个是隐藏字段，第二个是undolog日志,第三个是readView读视图,

隐藏字段是指:在mysql中给每个表都设置了隐藏字段,有一个是trx_id(事务id)，记录每一次操作的事务id，是自增的;另一个字段是roll_pointer(回滚指针)，指向上一个版本的事务版本记录地址

undolog主要的作用是记录回滚日志，存储具体的老版本数据，在内部会形成一个版本链，记录不同事务修改数据的版本，通过roll_pointer指针形成一个链表，提供查询功能

readView是一个数据结构，解决的是一个事务查询选择版本的问题，在内部定义了一些匹配规则和当前的一些事务id判断该访问那个版本的数据，不同的隔离级别快照读是不一样的，最终的访问的结果不一样。如果是rc隔离级别，每一次执行快照读时生成ReadView，如果是rr隔离级别仅在事务中第一次执行快照读时生成ReadView，后续复用

❓ 常见误解澄清

误解1：“Read View 能直接访问旧版本，为什么还要Undo Log？”

• 错误：Read View 本身不存储数据！它只是一个事务快照（内存中的数据结构）。

• 真相：Read View 通过DB_ROLL_PTR 去 Undo Log 中找数据。

  例如：Read View 说“版本ID=100可见”，但必须调用 DB_ROLL_PTR 从Undo Log中取出ID=100的版本。

误解2：“Undo Log 保存了所有版本，Read View 为什么还要判断？”

• 错误：Undo Log 是“仓库”，但仓库里可能有未提交的版本（如T2的修改）。
• 真相：Read View 的规则过滤了这些无效版本，确保事务只看到已提交的数据。

6 种会发生索引失效的情况：

• 当我们使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效；
• 当我们在查询条件中对索引列使用函数，就会导致索引失效。
• 当我们在查询条件中对索引列进行表达式计算，也是无法走索引的。
• MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
• 联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。
• 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。

日志分析工具mysqldumpslow

在生产环境中，如果要手工分析日志，查找、分析SQL，显然是个体力活，MySQL提供了日志分析工具mysqldumpslow。比如有100条慢sql，如何快速找出出现频次最高的前5条。

查看mysqldumpslow的帮助文档

在Linux命令行窗口执行mysqldumpslow –help

常用命令案例

日志文件地址：/var/lib/mysql/slow.log

# 得到返回记录集最多的10个SQL
mysqldumpslow -s r -t 10 /var/lib/mysql/slow.log
 
# 得到访问次数最多的10个SQL
mysqldumpslow -s c -t 10 /var/lib/mysql/slow.log
 
# 得到按照时间排序的前10条里面含有左连接的查询语句
mysqldumpslow -s t -t 10 -g "left join" /var/lib/mysql/slow.log

# 另外建议使用这些命令时结合|和more使用，否则出现爆屏的情况
mysqldumpslow -s r -t 10 /var/lib/mysql/slow.log | more

主从同步原具体详细过程如下：

• MySQL 主库在收到客户端提交事务的请求之后，会先写入 binlog，再提交事务，更新存储引擎中的数据，事务提交完成后，返回给客户端“操作成功”的响应。
• 从库会创建一个专门的 I/O 线程，连接主库的 log dump 线程，来接收主库的 binlog 日志，再把 binlog 信息写入 relay log 的中继日志里，再返回给主库“复制成功”的响应。
• 从库会创建一个用于回放 binlog 的线程，去读 relay log 中继日志，然后回放 binlog 更新存储引擎中的数据，最终实现主从的数据一致性。

end