高速查找术 —— B+树索引原理

假设你经营一个图书馆，有100万本书。有读者来问”有没有《算法导论》？“你会从第一个书架开始一本本找吗？当然不会——你会去查索引卡片柜。MySQL中的索引，就是数据库的”索引卡片柜”。

📋 开篇自测：你已经知道多少？

1. 没有索引的情况下，MySQL查找一条记录需要怎样操作？为什么慢？
2. B+树和二叉搜索树有什么本质区别？为什么数据库选择B+树？
3. “回表”是什么意思？怎样避免回表？

---

一、没有索引的世界——全表扫描的痛苦

上一章我们知道了，数据存储在一个个16KB的数据页中，页与页之间通过双向链表串联，页内的记录通过单向链表按主键排序。

假设我们有一张百万行的用户表：

CREATE TABLE users (
    id INT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(50),
    email VARCHAR(100),
    city VARCHAR(50),
    age INT
);
-- 假设已经有100万条数据

现在执行：

SELECT * FROM users WHERE city = '杭州';

city列上没有索引。MySQL会怎么做？

1. 从第一个数据页开始
2. 在页内逐条遍历记录，检查city是否等于’杭州’
3. 处理完这一页，通过FIL_PAGE_NEXT跳到下一页
4. 重复上述步骤，直到所有数据页都遍历完

这就是全表扫描（Full Table Scan）。如果表有100万行，平均每行200字节，大约需要12000多个数据页，也就是约200MB的数据。每一页都要从磁盘读取（假设没有缓存），每次磁盘I/O大约10ms……这可能需要好几秒甚至十几秒。

全表扫描的时间复杂度是O(N)。对于小表无所谓，但数据量一大就完全不可接受。

🤔 想一想 如果你有一本1000页的字典，但没有拼音索引和部首索引，要找到”鳄”字需要怎么做？有了索引后呢？

---

二、索引的底层数据结构——为什么是B+树

为了加速查找，数据库需要一种高效的数据结构。让我们一步步推演出B+树。

方案一：有序数组 + 二分查找

把数据按键值排好序，用二分查找定位——时间复杂度O(log N)，很快！

但问题是：插入一条新数据时，需要移动大量元素来维持有序性。对于频繁增删改的数据库来说，这个代价太大了。

方案二：二叉搜索树

二叉搜索树（BST）的查找、插入、删除都是O(log N)。问题在于：

1. 极端情况下会退化为链表（O(N)）
2. 即使是平衡的，100万条数据意味着树的高度约为20层。每一层可能需要一次磁盘I/O，20次磁盘I/O还是太慢了

方案三：B树

既然二叉树太”瘦高”了（每个节点最多2个子节点），那就让每个节点多装一些数据，让树变得”矮胖”。

B树的每个节点可以存放多个键值和多个子节点指针。如果每个节点能存1000个键值，那3层B树就能索引10亿条数据。3次磁盘I/O就够了！

最终方案：B+树

B+树是B树的改良版，也是InnoDB实际使用的索引结构。它和B树的核心区别有两点：

区别一：数据只存在叶子节点

在B树中，每个节点都存储完整的数据。在B+树中，内部节点（非叶子节点）只存储键值和指针，所有真实数据都存放在叶子节点中。

这样做的好处：内部节点不存数据，能容纳更多的键值和指针，使得树更加”矮胖”，减少磁盘I/O次数。

区别二：叶子节点之间有双向链表

B+树的叶子节点通过双向链表相连。这使得范围查询变得极其高效——找到起点后，沿着链表顺序遍历即可，不需要回到树的上层。

                    ┌─────────────────┐
                    │   [30]  [60]    │  ← 根节点（内部节点）
                    └──┬──────┬───┬──┘
                       │      │   │
            ┌──────────┘      │   └──────────┐
            ↓                 ↓              ↓
    ┌───────────┐     ┌───────────┐   ┌───────────┐
    │ [10][20]  │     │ [35][50]  │   │ [70][80]  │  ← 内部节点
    └─┬──┬──┬──┘     └─┬──┬──┬──┘   └─┬──┬──┬──┘
      │  │  │           │  │  │        │  │  │
      ↓  ↓  ↓           ↓  ↓  ↓        ↓  ↓  ↓
    ┌──┐┌──┐┌──┐     ┌──┐┌──┐┌──┐   ┌──┐┌──┐┌──┐
    │..││..││..│ ←→  │..││..││..│←→ │..││..││..│  ← 叶子节点
    └──┘└──┘└──┘     └──┘└──┘└──┘   └──┘└──┘└──┘     (存完整数据)
         叶子节点之间通过双向链表相连

用数字来感受B+树的威力

假设：

• 每个数据页16KB
• 以INT主键为例，内部节点中每个键值占4字节，每个指针占6字节，每对占10字节
• 一个内部页面大约可以存1600个键值指针对（这是近似估算，忽略了页头等固定开销，实际值略小。如果是BIGINT主键，每对14字节，约可存1100个）
• 叶子节点每行数据200字节，每页约存80行

那么：

• 2层B+树：1600 × 80 = 12.8万行
• 3层B+树：1600 × 1600 × 80 = 约2亿行
• 4层B+树：1600 × 1600 × 1600 × 80 = 约3276亿行

3次磁盘I/O就能在2亿条记录中精确定位一条数据。 而且根节点通常常驻内存，实际只需2次磁盘I/O。这就是B+树的威力。

---

三、聚簇索引——数据和索引住在一起

InnoDB中有一种特殊的索引叫聚簇索引（Clustered Index）。它的特殊之处在于：叶子节点直接存储了完整的行数据。

在InnoDB中，数据就是按照聚簇索引的顺序来组织的。换句话说，聚簇索引的叶子节点就是数据页。

聚簇索引结构（以主键id为例）：

内部节点:  [id=30的指针] [id=60的指针]
                ↓
叶子节点:  [id=1, name='张三', age=25, ...]  ← 完整行数据
          [id=2, name='李四', age=30, ...]
          [id=3, name='王五', age=22, ...]
          ...

每张InnoDB表有且只有一个聚簇索引。 聚簇索引的键值就是表的主键。

那如果你建表时没定义主键呢？InnoDB会这样选择聚簇索引的键值：

1. 如果有PRIMARY KEY，就用它
2. 如果没有，找第一个NOT NULL的UNIQUE索引
3. 如果还没有，InnoDB会自动生成一个隐藏的DB_ROW_ID列作为聚簇索引的键值

这就是为什么我们建议每张表都显式定义一个主键——让你掌控数据的组织方式。

-- 推荐：显式定义主键
CREATE TABLE products (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(200),
    price DECIMAL(10,2)
);

🤔 想一想 既然聚簇索引决定了数据的物理存储顺序，那聚簇索引的键值选择会怎样影响插入性能？自增整数 vs UUID，哪个做主键更好？为什么？

---

四、二级索引——另外一套索引卡片

聚簇索引只有一个，而且只能根据主键来查找。如果要按city来查找用户呢？

这时候就需要二级索引（Secondary Index），也叫辅助索引或非聚簇索引。

-- 在city列上创建二级索引
CREATE INDEX idx_city ON users(city);

二级索引也是一棵B+树，但它的叶子节点不存储完整的行数据，只存储索引列的值和对应的主键值。

二级索引（idx_city）结构：

内部节点:  [城市='南京'] [城市='武汉']
                ↓
叶子节点:  [city='北京', id=5]  [city='北京', id=23]
          [city='杭州', id=3]  [city='杭州', id=17]
          [city='深圳', id=8]  [city='深圳', id=42]
          ...

回表——二级索引的”两步走”

当你执行 SELECT * FROM users WHERE city = '杭州'; 时，使用二级索引idx_city的过程是：

第一步：在二级索引中查找。 通过B+树定位到city='杭州'的叶子节点，得到对应的主键值：id=3, id=17, ...

第二步：回聚簇索引查完整数据。 拿着主键值，再去聚簇索引中查找完整的行数据。

第二步就是回表（Back to Table）。每找到一个匹配的记录，就要回聚簇索引查一次。如果匹配的记录很多，回表的成本可能会很高。

二级索引B+树               聚簇索引B+树
    │                          │
    ↓                          ↓
[city='杭州', id=3]  ─→  [id=3, name='王五', city='杭州', age=22, ...]
[city='杭州', id=17] ─→  [id=17, name='赵六', city='杭州', age=35, ...]
    回表!                    回表!

---

五、覆盖索引——省去回表的妙招

如果查询需要的所有列都已经在索引中了，那就不需要回表了。这种情况叫覆盖索引（Covering Index）。

-- 假设有索引 idx_city
-- 这个查询只需要city和id（主键），都在二级索引中，不需要回表
SELECT id, city FROM users WHERE city = '杭州';

-- 这个查询需要name列，不在idx_city索引中，需要回表
SELECT id, city, name FROM users WHERE city = '杭州';

为了让更多查询能用上覆盖索引，我们可以创建联合索引：

-- 创建联合索引（覆盖city、age、name三个字段）
CREATE INDEX idx_city_age_name ON users(city, age, name);

-- 这个查询现在可以走覆盖索引了，不需要回表
SELECT city, age, name FROM users WHERE city = '杭州' AND age > 25;

使用EXPLAIN可以判断查询是否用到了覆盖索引——如果Extra列显示Using index，说明走了覆盖索引。

EXPLAIN SELECT id, city FROM users WHERE city = '杭州';
-- Extra: Using index  ← 覆盖索引，无需回表

⚠️ 常见误区 误区一：索引越多越好。 每个索引都是一棵独立的B+树，占用额外磁盘空间。更重要的是，每次INSERT、UPDATE、DELETE都需要维护所有索引，索引越多，写入性能越差。索引是一种”空间和写入性能换读取性能”的权衡。

误区二：只要WHERE条件中的列有索引就一定会用。 MySQL的优化器会评估使用索引的成本和全表扫描的成本。如果优化器估算使用索引反而更慢（比如查询结果占全表大部分数据），它会选择全表扫描。

---

六、联合索引与最左前缀原则

联合索引是在多个列上创建的一个索引。它的排序规则是：先按第一个列排序，第一个列相同的再按第二个列排序，以此类推。

CREATE INDEX idx_city_age ON users(city, age);

这个联合索引的B+树叶子节点大致是这样排列的：

[city='北京', age=20, id=15]
[city='北京', age=25, id=8]
[city='北京', age=30, id=42]
[city='杭州', age=22, id=3]
[city='杭州', age=28, id=17]
[city='深圳', age=24, id=31]
[city='深圳', age=35, id=9]

注意：数据是先按city排序，city相同的情况下再按age排序。

最左前缀原则

因为这种排序规则，联合索引的使用有一个”最左前缀原则”：查询条件必须从索引的最左列开始连续使用，索引才能生效。

-- 能用 idx_city_age 索引
SELECT * FROM users WHERE city = '杭州';                    -- 用了最左列city
SELECT * FROM users WHERE city = '杭州' AND age > 25;       -- 用了city和age
SELECT * FROM users WHERE city = '杭州' AND age = 28;       -- 用了city和age

-- 不能用 idx_city_age 索引
SELECT * FROM users WHERE age > 25;                         -- 跳过了city
-- （age只在各自的city内有序，全局并不有序）

打个比方：联合索引(city, age)就像一本先按城市名的拼音排序、再按年龄排序的通讯录。你可以快速翻到”杭州”（用city过滤），然后在”杭州”内部快速找到28岁的人（用age过滤）。但如果你直接说”找28岁的人”，这本通讯录帮不了你——28岁的人分散在各个城市中，没有全局排序。

索引列顺序的选择

设计联合索引时，列的顺序很重要。一般原则是：

1. 区分度高的列放前面：区分度 = 不同值的数量 / 总行数。性别列（男/女）区分度低，邮箱列区分度高
2. 频繁出现在等值查询中的列放前面
3. 范围查询的列放后面（因为范围查询之后的列无法使用索引排序）

-- city等值查询 + age范围查询 → city在前，age在后
CREATE INDEX idx_city_age ON users(city, age);

-- 对于这个查询，city和age都能用上索引
SELECT * FROM users WHERE city = '杭州' AND age > 25;

-- 如果反过来 idx_age_city，只有age能用上（range之后的city用不上）

🤔 想一想 假设有索引idx_a_b_c(a, b, c)，以下哪些查询能完全利用这个索引？

• WHERE a = 1 AND b = 2 AND c = 3
• WHERE a = 1 AND c = 3
• WHERE b = 2 AND c = 3
• WHERE a = 1 AND b > 2 AND c = 3

---

七、索引的实际应用建议

哪些列适合建索引

-- 1. WHERE条件中频繁使用的列
CREATE INDEX idx_email ON users(email);

-- 2. JOIN关联条件的列
CREATE INDEX idx_dept_id ON employees(department_id);

-- 3. ORDER BY排序的列
CREATE INDEX idx_created_at ON orders(created_at);

-- 4. GROUP BY分组的列
CREATE INDEX idx_category ON products(category);

哪些列不适合建索引

• 极少用于查询条件的列
• 区分度极低的列（如”性别”列只有2个值）
• 频繁更新的列（每次更新都要维护索引）
• 数据量很小的表（全表扫描可能更快）

索引失效的常见场景

-- 1. 对索引列使用函数
SELECT * FROM users WHERE YEAR(created_at) = 2025;  -- 索引失效！
-- 改为：
SELECT * FROM users WHERE created_at >= '2025-01-01'
                    AND created_at < '2026-01-01';

-- 2. 隐式类型转换
-- phone列是VARCHAR类型，但用数字去查
SELECT * FROM users WHERE phone = 13800138000;  -- 索引可能失效！
-- 改为：
SELECT * FROM users WHERE phone = '13800138000';

-- 3. LIKE以通配符开头
SELECT * FROM users WHERE name LIKE '%三';  -- 索引失效！
SELECT * FROM users WHERE name LIKE '张%';  -- 索引有效

-- 4. OR条件中部分列没有索引
SELECT * FROM users WHERE city = '杭州' OR age = 25;
-- 如果age没有索引，整个查询可能不走索引

⚠️ 常见误区 误区：建了索引就万事大吉。 索引需要维护。数据量变化后，索引的统计信息可能不准确，优化器可能做出错误的判断。可以用ANALYZE TABLE来更新统计信息。此外，索引碎片化也会影响性能，定期使用OPTIMIZE TABLE或ALTER TABLE ... ENGINE=InnoDB来整理。

---

📝 掌握度自测

1. B+树相比B树有哪两个核心区别？这两个区别分别带来了什么好处？
2. 聚簇索引和二级索引的叶子节点分别存储什么内容？
3. 什么是”回表”？什么是”覆盖索引”？如何通过设计索引来减少回表？
4. 最左前缀原则是什么？联合索引(a, b, c)能否加速WHERE b = 1的查询？为什么？
5. 列举至少3种会导致索引失效的情况。

💡 自我评估

• 答对5题：索引原理已经融会贯通，可以在实际项目中自信地设计索引了
• 答对3-4题：基础扎实，建议重点回顾联合索引和索引失效的场景
• 答对0-2题：索引是MySQL中最重要的优化手段，建议反复阅读，结合EXPLAIN实际验证