一、B 树索引的底层数据结构1.1 为什么是 B 树在深入 B 树之前先理解为什么 MySQL 选择它而不是其他数据结构数据结构磁盘 I/O 次数适用场景问题数组O(log n) 二分查找静态数据插入删除需要移动数据二叉搜索树O(log n) 但可能退化为 O(n)内存中树高度不可控磁盘 I/O 多AVL/红黑树O(log n) 但高度约 log₂(n)内存中2000万数据高度约25层B 树O(log_m n)m 为阶数磁盘存储非叶子节点也存数据B 树O(log_m n)更低的高度磁盘存储所有数据在叶子节点关键洞察磁盘 I/O 是数据库的瓶颈。B 树通过高扇出每个节点存储更多键将树高控制在 3-4 层。1.2 B 树的核心特征sql\-\- 示例一个 B 树索引结构 \-\- 阶数 m 5每个节点最多 5 个指针4 个键值 \[50, 100, 150\] \-\- 根节点 / | \ \ / | \ \ \[10,20,30,40\] \[60,70,80,90\] \[120,130,140\] \[160,170,180,190\] / | | | \ ... ... ... ... 叶子节点 ↓ ↓ ↓ ↓ ↓ \[数据\] \[数据\] \[数据\] \[数据\] \[数据\] \-\- 数据都在叶子B 树的核心特征特征说明优势所有数据在叶子节点内部节点只存键值和指针内部节点能存更多键 → 树更矮叶子节点形成链表叶子节点有指向下一个叶子节点的指针范围查询高效叶子节点存储数据根据数据存储方式分为聚簇/二级索引详见后文节点大小 页大小MySQL 默认 16KB一次 I/O 读取一页1.3 B 树的高度计算python\# 计算 B 树的高度以 InnoDB 为例 import math \# 参数 page_size 16 * 1024 \# 16KB key_size 8 \# BIGINT 类型键值 8 字节 pointer_size 6 \# 指针大小 6 字节 row_size 200 \# 估算每行数据 200 字节 \# 每个非叶子节点可存储的键数量 slot_size key_size pointer_size \# 14 字节 keys\_per\_node page_size // slot_size \# 16384 // 14 ≈ 1170 \# 每个叶子节点可存储的数据行数 rows\_per\_leaf page_size // row_size \# 16384 // 200 ≈ 81 \# 计算 3 层 B 树能存储的行数 \# 层1根1170 个指针 \# 层21170 * 1170 1,368,900 个指针 \# 层3叶子1,368,900 * 81 ≈ 110,880,900 行 print(f2层B树可存储约 {1170 * 81:,} 行) \# 约 94,770 行 print(f3层B树可存储约 {1170 * 1170 * 81:,} 行) \# 约 1.1 亿行结论B 树通常只有 2-4 层意味着查找任何数据只需要 2-4 次磁盘 I/O。1.4 B 树的查找过程sql\-\- 示例表 CREATE TABLE user ( id INT PRIMARY KEY, name VARCHAR(50), age INT, INDEX idx_age (age) ); \-\- 执行查询 SELECT * FROM user WHERE id 25;查找过程聚簇索引text1. 加载根节点到内存磁盘I/O #1根节点包含[10, 20, 30, 40, …] 的键值判断 25 在 20 和 30 之间 → 走第二个指针2. 加载第二层节点磁盘I/O #2该节点包含[21, 22, 23, 24, 25, 26, …]找到 25 对应的指针3. 加载叶子节点磁盘I/O #3读取包含 id25 的完整行数据返回结果二、聚簇索引 vs 二级索引2.1 核心区别特性聚簇索引二级索引数据存储位置叶子节点存储完整行数据叶子节点存储主键值每表数量只有 1 个可以有多个默认索引PRIMARY KEY 自动创建普通 INDEX / UNIQUE查询效率直接找到数据1次回表找到主键后需要回表占用空间较大存储完整行较小只存键主键2.2 聚簇索引结构sql CREATE TABLE student ( id INT PRIMARY KEY, \-\- 聚簇索引 name VARCHAR(50), class VARCHAR(20), score INT );聚簇索引的 B 树结构text内部节点只存键值 \[100, 200, 300, ...\] / | \ / | \ 叶子节点存完整行数据 ┌─────────────────────────────────────────────────────┐ │ 100 | nameAlice | classA | score95 │ ├─────────────────────────────────────────────────────┤ │ 101 | nameBob | classA | score87 │ ├─────────────────────────────────────────────────────┤ │ 102 | nameCarol | classB | score92 │ ├─────────────────────────────────────────────────────┤ │ ... → 下一个叶子节点 │ └─────────────────────────────────────────────────────┘查询过程sqlSELECT * FROM student WHERE id 101;-- 直接命中叶子节点一次 I/O 拿到所有数据2.3 二级索引结构sql-- 创建二级索引CREATE INDEX idx_name ON student(name);二级索引的 B 树结构text内部节点索引键值 指针[‘Bob’, ‘David’, ‘Frank’, …]/ |/ |叶子节点索引键值 主键值┌─────────────────────────────────────────────────────┐│ ‘Alice’ | 100 │├─────────────────────────────────────────────────────┤│ ‘Bob’ | 101 │├─────────────────────────────────────────────────────┤│ ‘Carol’ | 102 │└─────────────────────────────────────────────────────┘查询过程需要回表sqlSELECT * FROM student WHERE name ‘Bob’;-- 步骤1在二级索引 idx_name 中查找 ‘Bob’-- 找到主键值 101磁盘I/O #1-- 步骤2回表 - 用主键 101 到聚簇索引中查找完整数据-- 找到完整行磁盘I/O #22.4 覆盖索引避免回表sql-- 如果查询只需要索引中的字段无需回表SELECT name FROM student WHERE name ‘Bob’;-- ✅ 直接在 idx_name 的叶子节点就能拿到 name无需回表SELECT id, name FROM student WHERE name ‘Bob’;-- ✅ id 是主键也存储在 idx_name 的叶子节点SELECT * FROM student WHERE name ‘Bob’;-- ❌ 需要回表因为 * 包含 class 和 score覆盖索引示例sql-- 创建覆盖索引包含所有查询字段CREATE INDEX idx_name_score ON student(name, score);-- 下面的查询只需要这个索引无需回表SELECT name, score FROM student WHERE name ‘Bob’;SELECT id, name, score FROM student WHERE name ‘Bob’;三、最左匹配原则3.1 核心原理最左匹配原则MySQL 使用联合索引时会从左到右依次匹配查询条件遇到范围查询、、between、like后停止匹配。sql-- 创建联合索引CREATE INDEX idx_a_b_c ON table_name (a, b, c);-- 索引的排序结构-- 先按 a 排序a 相同再按 b 排序b 相同再按 c 排序3.2 索引排序可视化sql-- 表数据INSERT INTO test VALUES(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2);-- 联合索引 (a, b, c) 的排序结果(1,1,1) → (1,1,2) → (1,2,1) → (1,2,2) → (2,1,1) → (2,1,2) → (2,2,1) → (2,2,2)3.3 哪些查询走索引WHERE 条件是否走索引原因a 1✅ 走索引匹配第一列a 1 AND b 2✅ 走索引匹配前两列a 1 AND b 2 AND c 3✅ 走索引匹配全部三列b 2 AND c 3❌ 不走索引第一列缺失无法定位a 1 AND c 3⚠️ 部分索引a 过滤后c 无法用索引中间缺 ba 1 AND b 2⚠️ 部分索引a 是范围查询b 无法用索引a 1 AND b 2 AND c 3⚠️ 部分索引b 是范围查询c 无法用索引3.4 详细分析sql-- 场景1完美匹配 ✅SELECT * FROM test WHERE a 1 AND b 2 AND c 3;-- 索引定位(1,2,3) 精确位置-- 场景2左侧缺失 ❌SELECT * FROM test WHERE b 2 AND c 3;-- 无法使用索引因为不知道 a 的值无法定位起始位置-- 场景3中间缺失 ⚠️SELECT * FROM test WHERE a 1 AND c 3;-- 过程-- 1. 索引先按 a1 定位到范围-- 2. 但这个范围内b 有多种值c 不是有序的-- 3. 只能用于过滤 ac 需要回表后再过滤-- 场景4范围查询后的列失效 ⚠️SELECT * FROM test WHERE a 1 AND b 2 AND c 3;-- 过程-- 1. a1 定位-- 2. b2 范围查找找到所有 b2 的记录-- 3. 在这个范围内c 是无序的无法用索引-- 场景5使用 ORDER BY注意排序方向SELECT * FROM test WHERE a 1 ORDER BY b, c;-- ✅ 索引已经按 (a,b,c) 排序直接取数据无需 filesortSELECT * FROM test WHERE a 1 ORDER BY b DESC, c ASC;-- ❌ 排序方向不一致需要 filesort3.5 最佳实践sql-- 1. 等值查询在前范围查询在后-- 推荐CREATE INDEX idx_status_time ON orders (status, created_at);SELECT * FROM orders WHERE status ‘paid’ AND created_at ‘2024-01-01’;-- 不推荐CREATE INDEX idx_time_status ON orders (created_at, status);-- 原因时间范围查询后status 索引失效-- 2. 区分度高的列在前-- 假设 gender 只有 ‘M’/‘F’user_id 唯一-- 推荐CREATE INDEX idx_user_gender ON orders (user_id, gender);-- 不推荐CREATE INDEX idx_gender_user ON orders (gender, user_id);-- 3. 索引下推ICP - Index Condition Pushdown-- MySQL 5.6 支持可以在索引层面过滤减少回表四、索引失效场景完整清单4.1 失效场景速查表失效场景示例原因函数操作WHERE YEAR(date) 2024索引存储的是原值不是函数结果类型转换WHERE phone 13800138000phone是varchar隐式转换函数操作计算操作WHERE age 1 25对索引列计算LIKE ‘%abc’WHERE name LIKE %Bob通配符在前无法匹配B树排序OR 条件WHERE a 1 OR b 2OR 两边的列都需要索引NOT 条件WHERE a ! 1/WHERE NOT (a1)范围太大优化器认为全表扫描更快IS NULL / IS NOT NULLWHERE a IS NULL取决于 NULL 值比例使用 ! 或 WHERE a 1同 NOT 条件联合索引未用最左列WHERE b 1 AND c 2无法定位起始位置范围查询后的列WHERE a 1 AND b 2 AND c 3范围后列无序4.2 详细示例sql\-\- 表结构 CREATE TABLE user ( id INT PRIMARY KEY, name VARCHAR(50), age INT, email VARCHAR(100), phone VARCHAR(20), create_date DATE, INDEX idx_name (name), INDEX idx_age (age), INDEX idx_phone (phone), INDEX idx_date (create_date), INDEX idx\_name\_age (name, age) ); \-\- ❌ 1\. 对索引列使用函数 EXPLAIN SELECT * FROM user WHERE LOWER(name) bob; \-\- 解决存储时统一小写或使用虚拟列 \-\- ❌ 2\. 隐式类型转换 EXPLAIN SELECT * FROM user WHERE phone 13800138000; \-\- phone 是 VARCHAR \-\- 实际执行WHERE CAST(phone AS SIGNED) 13800138000 \-\- ❌ 3\. 对索引列进行计算 EXPLAIN SELECT * FROM user WHERE age 1 25; \-\- 改写为WHERE age 24 \-\- ❌ 4\. LIKE 前缀模糊匹配 EXPLAIN SELECT * FROM user WHERE name LIKE %Bob%; \-\- ✅ 可以使用WHERE name LIKE Bob% \-\- ❌ 5\. OR 条件两边都需要独立索引 EXPLAIN SELECT * FROM user WHERE name Bob OR age 25; \-\- 解决UNION 或使用 IN (如果可能) \-\- ✅ OR 的替代方案 SELECT * FROM user WHERE name Bob UNION SELECT * FROM user WHERE age 25; \-\- ❌ 6\. NOT 条件 EXPLAIN SELECT * FROM user WHERE name ! Bob; \-\- ❌ 7\. 联合索引未使用最左列 EXPLAIN SELECT * FROM user WHERE age 25; \-\- idx\_name\_age 无效 \-\- 虽然 age 是索引第二列但无法使用 \-\- ❌ 8\. 范围查询后的列 EXPLAIN SELECT * FROM user WHERE name Bob AND age 25; \-\- 这个例子中 age 是范围但如果后面还有列后面列会失效 \-\- ⚠️ 9\. 数据分布不均优化器选择 \-\- 如果表中 99% 的数据 age 10MySQL 可能选择全表扫描 EXPLAIN SELECT * FROM user WHERE age 10;4.3 特殊情况看似失效实则有效sql\-\- 1\. IS NULL 在某些情况下有效 EXPLAIN SELECT * FROM user WHERE name IS NULL; \-\- 如果 NULL 值很少可能走索引 \-\- 2\. 使用索引列排序且无 WHERE EXPLAIN SELECT * FROM user ORDER BY name; \-\- 可以走索引但可能不如 filesort 快 \-\- 3\. IN 查询可以走索引 EXPLAIN SELECT * FROM user WHERE name IN (Bob, Alice, Tom); \-\- IN 相当于多个等值查询 \-\- 4\. BETWEEN 对等值查询有效 EXPLAIN SELECT * FROM user WHERE age BETWEEN 20 AND 30; \-\- 范围查询但后面的列会失效4.4 实战优化 SQL 示例sql\-\- 原 SQL各种问题 SELECT * FROM orders WHERE YEAR(create_time) 2024 AND status ! cancelled AND amount 10 100 AND user_phone 13800138000 \-\- phone 是 VARCHAR ORDER BY create_time DESC; \-\- 优化后 CREATE INDEX idx\_create\_time_status ON orders(create_time, status); CREATE INDEX idx\_user\_phone ON orders(user_phone); SELECT * FROM orders WHERE create_time 2024-01-01 AND create_time 2025-01-01 AND status IN (pending, paid, shipped) \-\- 排除 cancelled AND amount 90 \-\- 移除了计算 AND user_phone 13800138000 \-\- 字符串 ORDER BY create_time DESC;五、总结与最佳实践5.1 核心要点速记textB 树特征├── 所有数据在叶子节点├── 叶子节点形成双向链表└── 高度通常 2-4 层聚簇索引├── 每表唯一叶子存完整行└── 主键自动创建二级索引├── 每表多个叶子存主键└── 查询需要回表最左匹配├── 联合索引从左到右匹配├── 等值查询先于范围查询└── 遇到范围查询后失效失效场景├── 函数/计算/类型转换├── LIKE ‘%xx’├── OR 两边都要索引└── 联合索引缺左列5.2 设计建议场景建议主键选择使用自增 BIGINT避免 UUID插入随机页分裂严重索引数量单表不超过 5-6 个维护成本高选择性索引列区分度越高越好性别类不适合单独建索引覆盖索引高频查询字段建覆盖索引避免回表顺序等值查询列在前范围查询列在后5.3 验证方法sql-- 使用 EXPLAIN 分析查询EXPLAIN SELECT * FROM user WHERE name ‘Bob’;-- 关键字段-- type: const ref range index ALL越左越好-- key: 实际使用的索引名-- rows: 扫描行数越小越好-- Extra: Using index覆盖索引、Using filesort需要排序-- 使用 FORCE INDEX 测试SELECT * FROM user FORCE INDEX(idx_name) WHERE name ‘Bob’;-- 查看索引使用情况SHOW INDEX FROM user;