# MySQL|计算机基础篇

> 本文系统介绍了MySQL的索引原理（B+树结构、与红黑树对比、磁盘I/O优化）、索引类型及其在数据库查询优化中的作用，帮助读者理解MySQL高效存储与检索数据的核心机制，适合面试准备和基础学习。

- 原文：https://feinterview.poetries.top/docs/fe-base-docs/compute-docs/MySQL
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2026.10.08
- 可见范围：免费部分

---

## 一、索引

- 索引就是书的目录：用额外的空间和写入成本，换查询时不用一页页翻（全表扫描）
- 索引在存储引擎层实现，`InnoDB` 默认用 `B+ Tree`：矮、胖、叶子有序相连，等值、范围、排序都能用
- `InnoDB` 主键是聚簇索引，叶子存整行；二级索引叶子存主键值，查别的列要回表
- 联合索引看最左前缀；查询的列都在索引里就是覆盖索引，不用回表
- 常见失效：索引列上套函数、隐式类型转换、`LIKE '%xx'` 前置通配符；索引也不是越多越好，每个都拖慢写入

**索引可以理解成书的目录，它用额外的存储空间和写入时的维护成本，换来查询时不用一行行扫全表。** `MySQL` 里索引是存储引擎实现的，`InnoDB` 默认用 `B+ Tree`，树很矮，三四层就能装下千万级数据，叶子节点还按顺序串起来，所以范围查询和排序也能用上。`InnoDB` 的主键索引叶子里直接存整行数据，叫聚簇索引；二级索引叶子里存的是主键值，查到之后还得拿主键再去主键索引里取一次，叫回表。我做索引设计时主要看三件事：查询条件和联合索引的列顺序对不对得上，能不能做成覆盖索引省掉回表，以及这张表写得多不多，别为了读把写拖垮。

## B+ Tree 原理

- **订单表 `phone` 是 `VARCHAR` 而且建了索引，`WHERE phone = 13800138000` 却全表扫描，为什么？**

  字符串列拿数字去比，`MySQL` 会把每一行的 `phone` 转成数字再比较，相当于在索引列上套了函数，索引就用不上了。写成 `WHERE phone = '13800138000'`。

- **`WHERE DATE(created_at) = '2026-10-01'` 很慢，`created_at` 明明有索引，怎么改？**

  对索引列套函数后，`B+ Tree` 里存的是原值，没法按 `DATE()` 的结果定位。改成范围：`created_at >= '2026-10-01' AND created_at < '2026-10-02'`。

- **一张只有几百行的配置表，加了索引 `EXPLAIN` 还是 `ALL`，索引白建了？**

  数据太少时，优化器算出来全表扫描比走索引再回表还便宜，就直接扫了，这很正常。小表本来也不用太纠结索引。

- **有人给一张写入很频繁的日志表的每一列都加了索引，有什么问题？**

  每次 `INSERT` 都要同时维护所有索引的 `B+ Tree`，写入变慢、占用空间翻倍，而且大部分索引根本用不上。只给真实查询条件建索引，上线前用 `EXPLAIN` 确认。

- **怎么确认一条 `SQL` 到底有没有用上索引？**

  `EXPLAIN` 看 `type`（`const`、`ref`、`range` 好，`ALL` 是全表扫描）、`key`（实际用的索引）、`rows`（预估扫描行数），`Extra` 里出现 `Using index` 说明是覆盖索引。`MySQL 8.0.18` 以后还能用 `EXPLAIN ANALYZE` 看真实耗时。

### 1. 数据结构

- `B Tree` = 平衡多路查找树，所有叶子在同一层，任何一条数据查找路径一样长
- `B+ Tree` 两点改进：数据只放叶子，内部节点只存键当路标；叶子之间用指针串成有序链表
- 内部节点不存数据 → 一页能塞更多键，扇出大、树更矮，磁盘 `I/O` 更少
- 范围查询 = 先从根走到起点叶子（`O(log N)`），再顺着链表往后读，不用回到根
- `InnoDB` 一页 `16KB`，三层 `B+ Tree` 大约能存两千万行，这是估算值不是定数

**`B Tree` 是所有叶子都在同一层的多路平衡查找树，`B+ Tree` 在它基础上做了两件事：数据只放在叶子，叶子之间用指针串起来。** 第一点让内部节点只存键和子指针，一个 `16KB` 的页能放上千个分支，树就特别矮；第二点让范围查询不用来回爬树，找到起点后顺着叶子链表往后读就行。比如查 `price BETWEEN 20 AND 50`，先从根往下找到第一个 `>= 20` 的叶子，再沿链表一直读到超过 `50` 为止。所以范围查询的代价是「定位起点 + 读结果条数」，结果越多越慢，不是什么 `O(1)`。

B Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。

B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。

在 B+ Tree 中，一个节点中的 key 从左到右非递减排列，如果某个指针的左右相邻 key 分别是 key<sub>i</sub> 和 key<sub>i+1</sub>，且不为 null，则该指针指向节点的所有 key 大于等于 key<sub>i</sub> 且小于等于 key<sub>i+1</sub>。

<div align="center"> <img src="https://s.poetries.top/cos/202203272133474.png" width="350px"> </div><br>

**原理拆解：** `B+ Tree` 通过高扇出节点把有序键空间逐层切分。查找一个键时，先在根节点比较分隔键并选择子指针，再在下一层重复，直到到达叶子节点；树始终保持平衡，所以任意叶子的访问层数基本一致。典型实现中，内部节点主要保存分隔键和子指针，完整记录或记录定位信息集中在叶子节点，这使单个内部节点能容纳更多分支，从而降低树高。

**查询链路：** 查找区间 `[20, 50]` 时，先按单点查找方式定位第一个不小于 `20` 的叶子位置，然后沿叶子之间的顺序指针持续扫描，读到大于 `50` 的键后停止。其代价可理解为定位起点的 `O(log_f N)` 加返回结果的线性读取量 `O(k)`，其中 `f` 是节点扇出、`k` 是命中记录数；顺序指针减少的是重复从根定位后续键的成本，并不会令范围查询变成 `O(1)`。

**边界与反例：** 内部节点分隔区间采用左闭右开、右侧最小键或其他约定，取决于具体实现，不能仅凭相邻键就断言两端都包含。大量相同键还需要配合记录标识或溢出组织方式维持确定顺序。平衡也不代表没有维护成本：插入导致节点溢出时可能分裂并向父节点传播，删除后则可能发生合并或重新分配。

**工程验证：** 在数据库中可用 `EXPLAIN` 对比等值查询、连续范围查询和对索引列施加函数后的查询计划，观察是否选择目标索引、预估扫描行数及是否出现额外排序。验证时还应保证统计信息可用并扩大数据量；小表上优化器选择全表扫描可能只是成本估算结果，不能据此判定 `B+ Tree` 索引失效。

- **`B Tree` 和 `B+ Tree` 都是平衡多路树，数据库为什么偏偏选 `B+ Tree`？**

  `B Tree` 内部节点也存数据，一页能放的键就少，树更高；范围查询还要中序遍历在不同层之间来回跳。`B+ Tree` 内部节点只当路标、叶子有序成链，树更矮，范围扫描就是顺着链表读。

- **三层的 `B+ Tree` 大概能存多少行，怎么估出来的？**

  按 `InnoDB` 一页 `16KB` 算，主键 `BIGINT` 占 `8` 字节加指针 `6` 字节，一个内部节点约 `1170` 个分支；叶子假设一行 `1KB`，一页放 `16` 行。`1170 × 1170 × 16` 约等于两千万，实际随行宽和填充率变化。

- **有人说叶子之间有链表，所以范围查询是 `O(1)`，对吗？**

  不对。先要从根走到起点叶子，这一步是 `O(log N)`，然后读 `k` 条结果就是 `O(k)`，查一万条和查十条的耗时差别很大。链表省的是每读一条都从根重新找的成本。

- **主键查询和二级索引查询，走的 `B+ Tree` 一样吗？**

  不是一棵树。`InnoDB` 每个索引都是一棵独立的 `B+ Tree`，主键树叶子存整行，二级索引树叶子存主键值，所以二级索引查到主键后还要去主键树再走一遍。

- **`B+ Tree` 的叶子节点之间是单向链表还是双向链表？**

  `InnoDB` 里同一层的页之间是双向链表，所以 `ORDER BY id DESC` 也能直接从右往左扫，不需要额外排序。

### 2. 操作

- 查找：从根开始，每个节点内二分找到下一层的指针，一路走到叶子，再在叶子里二分定位
- 每层一般就是一次页读取，树高 3~4 层 → 冷数据最多读 3~4 页，根和上层通常常驻缓存
- 插入：先找到目标叶子，页满了就分裂成两页，把分隔键推给父节点，极端时根分裂、树长高一层
- 删除：页太空时和兄弟合并或向兄弟借键；`InnoDB` 有合并阈值，不是每删一行就立刻重组
- 自增主键总在最右边追加，几乎不分裂；`UUID` 这种随机主键会到处插，页分裂多、碎片多

**`B+ Tree` 的查找就是从根节点开始，每层在节点里二分找到该往哪个子节点走，一直走到叶子。** 树高通常就三四层，而且上层节点基本都在内存里，所以一次主键查询实际的磁盘读取很少。插入和删除的麻烦在于要维持平衡：叶子页满了要分裂成两页，再把分隔键往父节点插，父节点也满了就继续往上分裂；删除让页太空时，会跟兄弟页合并或者借几个键过来。这也是为什么我建表时更喜欢自增主键，新数据永远追加在最右边的页，几乎不分裂，换成随机的 `UUID` 主键，插入会落到树的各个位置，频繁页分裂，写入变慢，空间也更碎。

进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。

插入删除操作会破坏平衡树的平衡性，因此在进行插入删除操作之后，需要对树进行分裂、合并、旋转等操作来维护平衡性。

**原理拆解：** `B+ Tree` 的内部节点只承担导航职责：节点中的分隔键把键空间划成多个区间，节点内二分确定下一页，再沿子指针下降。真正的索引记录集中在叶子层，叶子通常还通过双向链表相连，因此等值查询在叶子命中后结束，范围查询则可继续顺序扫描相邻叶子。树高为 `h` 时，冷缓存下通常要访问约 `h` 个索引页；缓存命中会减少物理 `I/O`，但不会改变逻辑下降路径。

**最小验证：** 输入一组无序主键，验证等值条件走唯一索引定位、范围条件从起点定位后连续扫描。

```sql
DROP TABLE IF EXISTS bpt_demo;
CREATE TABLE bpt_demo (
  id BIGINT PRIMARY KEY,
  payload VARCHAR(32) NOT NULL
) ENGINE=InnoDB;

INSERT INTO bpt_demo VALUES
  (40, 'd'), (10, 'a'), (70, 'g'),
  (20, 'b'), (60, 'f'), (30, 'c'), (50, 'e');

EXPLAIN SELECT payload FROM bpt_demo WHERE id = 30;
EXPLAIN SELECT id, payload
FROM bpt_demo
WHERE id BETWEEN 20 AND 50
ORDER BY id;
```

第一条预期显示 `const` 类型并使用 `PRIMARY`；第二条通常显示 `range`，结果按 `20、30、40、50` 返回。这里验证的是优化器选择和叶子有序性，不是直接观察节点分裂；小数据通常只有一个或少数页面。

**边界与排查：** 插入先定位目标叶子，页面空间不足时分裂并把分隔信息传播到父节点，极端情况下根也会分裂而使树高增加。删除后是否立即合并由存储引擎策略决定，不能把教科书中的每次欠载都理解成一次可见合并。顺序主键通常减少随机页分裂；随机主键可能增加页面离散和写放大。可结合 `EXPLAIN`、缓冲池命中率、页分裂相关引擎指标和实际延迟判断，不能仅凭复杂度推断磁盘访问次数。

- **主键从自增 `ID` 换成 `UUID` 之后，插入明显变慢，表也变大了，为什么？**

  自增主键每次都追加到最右边的叶子，页写满了开新页就行；`UUID` 是随机的，会插到中间已经满了的页里，触发页分裂，一页拆两页、每页只半满。想要全局唯一又有序，可以用雪花 `ID` 或者 `UUID v7` 这类按时间递增的方案。

- **一张一亿行的表，主键点查也就三四次页访问，为什么有时候还是很慢？**

  三四次是逻辑上要访问的页数，页不在 `Buffer Pool` 里就要读磁盘，冷数据或缓存被大查询挤掉时会慢很多。先看缓存命中率和是不是被锁等待卡住了，别急着怪索引。

- **删了半张表的数据，表文件一点没变小，是删除没生效吗？**

  删除生效了，但 `InnoDB` 只是把页里的空间标记成可复用，不会还给操作系统。要真正收缩文件，可以执行 `OPTIMIZE TABLE` 或者 `ALTER TABLE t ENGINE=InnoDB` 重建表，大表要挑低峰期做。

- **`B+ Tree` 插入时会像红黑树那样旋转吗？**

  不会。`B+ Tree` 保持平衡靠的是节点分裂、合并以及向兄弟节点借键，所有叶子天然在同一层，不需要旋转这种操作。

- **为什么根节点分裂的时候树会长高一层？**

  根满了只能拆成两个节点，再新建一个根指向它们，于是整棵树高度加一。这也是 `B+ Tree` 唯一长高的方式，所以它总是从上往下长，所有叶子始终在同一层。

### 3. 与红黑树的比较

- 时间复杂度都是 `O(log N)`，差别在底数：红黑树是二叉，`B+ Tree` 一个节点几百上千个分支
- 一亿个键：二叉树大约 `27` 层，扇出 `400` 的 `B+ Tree` 只要 `4` 层
- 数据库按页读磁盘，节点大小 = 一页，每走一层就是一次 `I/O` → 层数就是 `I/O` 次数
- 叶子有序且相邻存放，范围扫描能用上顺序读和磁盘预读；红黑树节点散落在各处，没有这个优势
- 纯内存、数据量不大的有序结构，红黑树更合适（`Java` 的 `TreeMap`、`Linux` 内核的调度队列都用它）

---

> 以上是免费部分。完整内容需要「前端进阶之旅」会员，原文：https://feinterview.poetries.top/docs/fe-base-docs/compute-docs/MySQL
