课程 10.4 · 阅读时间：~11 分钟

本课程详细解释了 B-tree 索引在 SQL 中的工作原理，包括物理和逻辑层面。您将了解结构由哪些节点组成，数据库管理系统如何遍历树，以及为什么这种方法能加速过滤和排序。我们将通过 Sakila 表进行实际示例，并巩固关键应用规则。到课程结束时，您将更好地理解何时 B-tree 索引确实能加速查询。

B-tree 索引是如何工作的

在上一课中，您学习了如何创建索引。现在我们来探讨索引内部的结构以及它为什么能加速搜索。

理解 B-tree 将帮助您识别索引何时真正有效以及何时无法使用。这一知识在优化慢查询时将非常有用。

什么是 B-tree 索引

B-tree 索引类似于书籍中的目录。您不需要逐页阅读，而是打开目录，找到所需的章节，然后直接前往。

B-tree 有三个层次：

• 根节点 - 搜索的起点，就像目录的封面；
• 中间节点 - 指示接下来该往哪个方向走；
• 叶子节点 - 包含所需的值和指向表中行的链接。

整个结构是排序的，因此数据库管理系统可以快速选择每个层次上的正确方向。

以下是其结构示意：

                    [ ROOT ]
                   /   |   \
                  /    |    \
            [NODE A] [NODE B] [NODE C]
            / |  \    / | \    / | \
           /  |   \  /  |  \  /  |  \
         [L1][L2][L3][L4][L5][L6][L7][L8]

每个节点包含帮助选择下一个节点的值。叶子节点 (L1–L8) 包含所需的数据。

如何执行 B-tree 搜索

当您搜索 WHERE last_name = 'SMITH' 时，数据库管理系统：

1. 从根节点开始；
2. 选择可能包含以 'S' 开头的姓氏的分支；
3. 向下移动，在每个层次上细化搜索；
4. 在叶子节点中找到所需的姓氏。

由于这个算法，搜索非常快速——即使在包含数百万行的表中，也只需检查几个层次。

B-tree 最擅长加速哪些操作

相等 (=)

B-tree 非常适合精确查找值。

SELECT
   customer_id,
   first_name,
   last_name
FROM customer
WHERE last_name = 'SMITH';

范围 (>, <, BETWEEN)

由于键的排序性，B-tree 对于范围条件非常有效。

SELECT
   payment_id,
   amount,
   payment_date
FROM payment
WHERE payment_date >= '2005-07-01'
  AND payment_date < '2005-08-01';

排序 (ORDER BY)

如果排序顺序与索引一致，数据库管理系统通常可以避免昂贵的单独排序。

SELECT
   payment_id,
   customer_id,
   payment_date
FROM payment
WHERE customer_id = 10
ORDER BY payment_date;

复合 B-tree 索引示例

我们将创建一个索引以适应常见的过滤和排序模式：

CREATE INDEX idx_payment_customer_date
ON payment (customer_id, payment_date);

检查计划：

EXPLAIN
SELECT
   payment_id,
   customer_id,
   payment_date,
   amount
FROM payment
WHERE customer_id = 10
  AND payment_date >= '2005-07-01'
ORDER BY payment_date;

结果：通常数据库管理系统会使用索引来根据 customer_id 进行过滤和 payment_date 的范围，并进行有序读取。

复合索引的左前缀规则

如果索引创建为 (customer_id, payment_date)，则数据库管理系统在条件中首先根据 customer_id 进行过滤时使用效果最佳。

效果好：

WHERE customer_id = 10

效果好：

WHERE customer_id = 10 AND payment_date >= '2005-01-01'

效果差：

WHERE payment_date >= '2005-01-01'

这个规则被称为“左前缀”：索引在您从左到右使用条件时效果最佳。

何时索引无效

索引不会被使用，如果：

• 您对列应用了函数：WHERE YEAR(payment_date) = 2005 — 索引无效；
• 在开头使用了通配符：WHERE name LIKE '%SMITH' — 索引无效；
• 条件过于宽泛并返回大量行 — 索引可能比读取整个表更慢。

效果差（函数妨碍索引）：

SELECT payment_id, payment_date
FROM payment
WHERE YEAR(payment_date) = 2005;

效果好（索引能够工作）：

SELECT payment_id, payment_date
FROM payment
WHERE payment_date >= '2005-01-01'
  AND payment_date < '2006-01-01';

实用建议

• 索引经常出现在 WHERE、JOIN、ORDER BY 中的字段。
• 对于复合索引，将最重要的过滤列放在第一位。
• 通过 EXPLAIN 检查索引的实际使用情况。
• 不要创建冗余索引：它们会增加写入成本。

本课程的关键要点：

• B-tree 是一种平衡结构，加速基于键的搜索。
• B-tree 的主要优势：相等、范围和按索引顺序排序。
• 复合索引遵循左前缀规则。
• 不合适的条件形式可能会使查询失去索引的优势。
• EXPLAIN 有助于理解 B-tree 是否在实际执行计划中被使用。

面试问题

为什么 B-tree 索引通常比全表扫描更快？

因为数据库管理系统通过树的分支找到所需的范围，所需的步骤是对数级别，而不是查看表中的所有行。

复合索引的左前缀规则是什么？

这个规则意味着优化器最好从键的第一个列开始使用索引，然后按顺序继续。

如何在实践中检查 B-tree 索引是否被使用？

需要执行 EXPLAIN 并查看访问类型、选择的键和执行阶段预期的行数。

在下一课中，我们将转向 SQL 查询的错误处理和调试技巧。