software

B-Tree 索引在 SQL 数据库中的工作原理：直观指南

发布: (2026年2月4日 GMT+8 02:51)
11 min read
原文: Dev.to

Source: Dev.to

Why Indexes Exist (The Real Problem)

关系型数据库在可靠地存储大量数据方面做了优化，但默认情况下并不一定针对高效搜索这些数据进行优化。当你在没有索引的情况下让数据库查找特定行时，它通常会执行 full table scan（全表扫描），逐行检查每一条记录。这在小规模时还能接受，但随着数据量的增长，速度会变得极其缓慢。

索引的存在就是为了避免这种蛮力做法。索引使数据库能够快速定位匹配数据所在的位置，而不必检查每一行。

B‑Tree 索引是大多数 SQL 数据库（PostgreSQL、MySQL/InnoDB、SQL Server、Oracle）的默认选择，因为它们在保持数据有序的同时，能够以受控且可预测的方式支持插入和更新。

直观感受——即使是 1000 万行数据，B‑Tree 索引通常也只需要几步比较就能找到单个值。定位一行是通过几次有针对性的 跳转 完成的，而不是遍历数百万条记录。写入操作确实会带来开销——每次插入都必须维护这种结构——但这种成本增长缓慢，使得 B‑Tree 能够极好地扩展。

什么问题由 B‑Tree 解决

数据结构搜索插入
已排序数组O(log n)（二分查找）O(n)（移动）
链表O(n)O(1)
B‑TreeO(log n)O(log n)（局部节点分裂）

B‑Tree 专为以下存储系统设计：

  • 保持数据有序，以支持范围查询和排序
  • 提供对数级别的搜索 (O(log n))
  • 通过浅而宽的结构最小化磁盘 I/O
  • 通过局部节点分裂支持高效写入

关键约束： 数据库以页为单位读取数据，而不是单行读取。

页面：数据库实际如何存储数据

在讨论 B‑Tree 之前，先了解一个基本概念很有帮助：数据库使用 页面（pages）。

  • 页面是固定大小的数据块（通常为 8 KB）。
  • 当数据库需要任何东西——一行记录、索引条目或指针——它会读取包含该内容的整个页面。

这适用于：

  • 表数据（实际的行）
  • 索引数据（B‑Tree 节点）

性能目标很简单：在每次页面读取时尽可能多地完成有用的工作。B‑Tree 节点被设计成恰好能装进一个页面，使数据库能够在每一次磁盘访问中取得巨大的进展。这种基于页面的模型是 B‑Tree 看起来与教材中的二叉树大相径庭的原因。

Page layout illustration

B‑树结构（高级）

B‑树由三层组成：

  1. 根节点 – 每次搜索的起点
  2. 内部节点 – 用于导航的路标
  3. 叶子节点 – 实际数据（或指针）所在的底层

属性

  • 已排序键 – 节点内部的键始终保持有序
  • 高扇出 – 每个节点包含许多键（通常是数百个），而不是仅两个
  • 平衡深度 – 所有叶子节点深度完全相同，确保无论查询哪个键都能获得可预测的性能

内部节点 vs. 叶子节点

  • 内部节点 包含键和指向子页的指针；仅用于导航。
  • 叶子节点 包含键和指向实际行的指针。

实现细节有所不同：

DBMSLeaf‑node payload
MySQL (InnoDB)Full row (clustered index)
PostgreSQLRow pointer (heap TID)

叶子节点通常会相互链接（从左到右），使数据库能够在不返回根节点的情况下执行范围扫描。

B‑Tree storing of data

如何进行查找

考虑以下查询：

SELECT * FROM users WHERE email = 'a@b.com';
  1. 从 根页 开始。
  2. 将搜索键与节点中的键进行比较，以找到正确的范围。
  3. 跟随子指针进入下一页。
  4. 重复上述过程，直到到达 叶子节点。
  5. 获取行指针（或整行数据）。

每一步都是一次 页读取，而不是逐行操作。

为什么 B‑树的高度保持较小

因为每个节点保存了许多键，树的增长是宽的，而不是高的。

典型数值：

  • 页面大小：8 KB
  • 键 + 指针：约40 字节
  • 每节点键数（分支因子）：约200

高度为 3 的树可以支持：

200³ ≈ 8,000,000 entries

因此，即使在大规模下，B‑树的查找仍然极其快速。

插入和节点分裂

当插入新行时，数据库必须更新 B‑Tree：

  1. 定位正确的 叶子节点。
  2. 如果节点还有空间，直接插入键（这很简单）。
  3. 如果节点已满，分裂它为两个节点。
  4. 将中间键提升到父节点。
  5. 分裂可能向上传播到根节点，但在实际中很少见。

这种平衡操作是为保持树在以后读取时高效而付出的 代价。

范围查询与排序

由于 B‑Tree 保持键的排序，它们能够实现高效的范围扫描：

SELECT * FROM orders
WHERE created_at BETWEEN '2025-01-01' AND '2025-01-31';
  • 使用标准查找定位第一个键 ('2025‑01‑01')。
  • 顺序遍历链接的叶子节点，直至达到范围的结束。

结果：

  • B‑Tree 原生支持 ORDER BY。
  • 它们支持前缀扫描（例如 LIKE 'abc%'）。
  • 哈希索引无法实现上述任意一种。

Composite Indexes

当您在多个列上创建索引，例如 (user_id, created_at)，B‑Tree 首先按 user_id 排序，然后按 created_at 排序。这种排序方式使得在前导列上进行过滤的查询能够受益于索引，并且当前导列固定时，也能对后续列进行高效的范围扫描。

B‑Tree 索引：何时表现出色，何时不适用

B‑Tree 的工作原理

  • 结构 – 一棵平衡树，每个节点保存一段键值范围以及指向子页的指针。
  • 搜索 – 从根节点开始，沿着相应的子指针向下，直到到达包含目标键的叶页为止。
  • 复杂度 – O(log N) 页读取，其中 N 为行数。由于页的大小与底层存储（例如 8 KB）相匹配，即使是非常大的表，树的高度也保持很低。

典型使用场景

场景为什么 B‑Tree 有帮助
主键查找 (WHERE id = …)对首列进行直接等值匹配。
范围扫描 (WHERE created_at BETWEEN …)树是有序的，能够顺序遍历匹配的叶子。
ORDER BY / GROUP BY 在已建索引的列上数据已经排序，省去额外的排序步骤。
前缀搜索 (WHERE name LIKE 'A%')前缀对应树中的连续范围。

复合（多列）索引

复合索引按照定义的列顺序存储。
示例：CREATE INDEX ix_user_created ON events (user_id, created_at);

  • 高效的查询

    • WHERE user_id = ?
    • WHERE user_id = ? AND created_at > ?（使用首列后，第二列进一步缩小范围）

  • 低效的查询

    • 单独 WHERE created_at = ? – 由于 created_at 不是首列，索引无法使用。

类比： 想象一本按 (姓氏, 名字) 排序的电话簿。定位所有 “Smith” 很容易，但要直接跳到每个 “John” 则必须扫描整本书。

常见误解

误区现实
“索引加速所有查询。”它们加快读取速度，但会给每个 INSERT、UPDATE 和 DELETE 增加开销。
“索引越多越好。”每个索引都会占用磁盘空间并增加写放大。
“B‑树只用于等值查询。”它们的真正优势在于处理 范围 并产生 排序输出。

当 B‑Tree 不是合适的选择

避免在以下情况下使用 B‑Tree 索引：

  1. 低基数 – 例如，对 90 % 行使用 is_active = true。优化器通常会倾向于全表扫描，因为读取索引再读取表的成本更高。
  2. 对唯一键的高频仅等值查找 – 哈希索引 可能更快（尽管灵活性较低）。
  3. 仅追加 / 时间序列数据 – 当行自然按时间排序且表非常大时，考虑使用 BRIN（块范围索引）。
  4. 全文搜索 – 使用 GIN 或其他为在大文本字段中搜索词汇而设计的倒排索引。

实用要点

  • B‑树是 页面优化 的，旨在最小化磁盘 I/O 而非 CPU 周期。
  • 树的高度 比总行数更重要；浅层树能够实现快速查找。
  • 复合索引中 列的顺序 至关重要；首列必须出现在查询的 WHERE 子句中，索引才有用。
  • 在添加新索引之前，务必权衡你的 读写比例——更多索引有利于读取，但会影响写入。
Back to Blog

相关文章

阅读更多 »