B 树 / B+ 树 / B* 树：从原理到 CRUD，再到数据库索引实战

Words 4008Read Time≈ 11 min
2026-2-11
cover
type
Post
status
Published
date
Nov 5, 2020 20:22
slug
summary
从磁盘 I/O 优化视角深入解析 B 树家族：讲解多路查找树如何用更宽更矮的结构减少磁盘访问，剖析 B 树的平衡约束与分裂/合并机制，对比 B+ 树如何通过叶子链表优化范围查询，介绍 B* 树的节点重分配策略，最后落地到 PostgreSQL、MySQL InnoDB 等数据库索引的实战应用场景，帮你理解为什么数据库索引几乎都选择 B 树家族。
tags
Data Structure
PostgreSQL
MySQL
category
Database
icon
password
wordCount
1440

前言

如果你曾经好奇：为什么数据库的索引几乎都绕不开 btree、为什么范围查询能跑得那么快、为什么插入会触发“页分裂”，答案大概率都在 B 树家族 里。
这篇文章会把 B 树（B-tree）、B+ 树（B+tree）、以及更偏优化取向的 B* 树（B*tree） 串起来讲清楚：它们都在做同一件事——用更少的磁盘 I/O 换来更稳定的查询性能。
🎯
你读完应当能带走三件事：
  • 为什么 B 类树是“为磁盘而生”的数据结构，以及它和 CPU 内存时代的二叉树有什么不同
  • B-tree、B+tree、B*tree 在结构与工程目标上的差异
  • 增删改查背后的“分裂 / 借位 / 合并”到底在维护什么约束

多路查找树（Multi-way Search Tree）

多路查找树（multi-way search tree）是一类“一个节点可以有多个孩子，并且一个节点里可以存多个关键字（key）”的查找树。
和普通二叉查找树相比，它打破了两个限制：
  • 孩子数不再只允许 2 个，可以是 3、5、上百个。
  • 一个节点不再只放 1 个关键字，而是放一串有序关键字。
这两个变化看似只是“变宽了”，但对磁盘访问非常关键：
💾
核心动机：减少 I/O 次数。
磁盘读取以“块（block/page）”为单位。让一个节点塞进一个磁盘块，节点里关键字越多，树的高度越低，查找时需要的 I/O 次数就越少。
B 树、B+ 树、B- 树都属于平衡的多路查找树家族。

B 树（B-Tree）

下面用“m 阶 B 树”描述其约束。

B 树的性质（更严谨版）

一个 m 阶 B 树通常满足（不同教材符号略有差异，这里取常见表述）：
  1. 若根节点不是叶子节点，则根至少有 2 个孩子。
  1. 除根以外的内部节点，孩子数在 ⌈m/2⌉ 到 m 之间。
  1. 内部节点若有 k 个孩子，则该节点包含 k-1 个关键字。
  1. 所有叶子节点在同一层（树是平衡的）。
  1. 节点内关键字有序，并把孩子子树的 key 范围分割开：
      • 第 i 个关键字左侧子树的 key 都小于它。
      • 右侧子树的 key 都大于它。

用人话翻译一下

  • 树会尽量“胖一点、矮一点”。
  • 每个节点里放一串有序 key，并用孩子指针把范围切成多段。
  • 任何插入删除都要遵守最小度数限制，否则就会触发“分裂 / 合并”来保持平衡。
B树

查询（Search）

查询过程本质上是“在节点内二分 + 决定走哪棵子树”，一路走到命中或到叶子。
查询
以查找 E 为例（字母序）：
  1. 比较根节点关键字 M。因为 E < M，走左子树。
  1. 在下一层节点关键字 D、G 中定位区间：D < E < G，所以走 D 与 G 之间对应的子树。
  1. 在叶子节点中找到 E，返回其指针信息。
🔍
你可以把它想象成：
在每个节点里做一次“小型二分查找”，然后决定下一步去哪一段。

插入（Insert）

插入要做两件事：
  • 找到应该落在哪个叶子节点。
  • 把 key 插进去后，如果节点“太满”，就要分裂并向上提升中间 key。
规则（以 m=5 为例）
  • 排序规则：节点内关键字始终有序。
  • 分裂规则：当一个节点关键字数 > m-1（这里 > 4）时，需要分裂。
    • 分裂时把“中间关键字”提升到父节点。
    • 左右两边关键字分别留在两个新节点里。
用 5 阶树（m=5）构造：插入 3、8、31、11、23、29、50、28
先插入 3、8、31、11：
插入
插入 23 后节点满了，触发分裂，把中间 key 11 提升，再插入 29：
删除
插入
再插入 50，最后插入 28 时右孩子再次满，分裂并把 29 提升到与 11 同层：
插入
🧠
分裂在保护什么？
它在保护“节点别太满、树别变高太快、并且所有叶子仍在同一层”。

删除（Delete）

删除比插入麻烦，因为“删掉之后可能太瘦”。一旦节点关键字数低于下限，就需要向兄弟节点借 key，借不到就合并。
规则（以 m=5 为例）
  1. 合并触发条件：关键字数 < ⌈m/2⌉ - 1（不同定义略有差异，你可以理解为“低于最低占用”就要处理）。
  1. 优先借、借不到再合并：
      • 先从相邻兄弟节点“借”一个 key（通过父节点调整分隔 key）。
      • 如果兄弟也不够借，就和兄弟合并，并把父节点的分隔 key 一起下沉。
🧯
删除在保护什么？
它在保护“节点别太空”，否则树会变得不平衡，查找性能也会不稳定。

B 树的特点（为什么适合磁盘）

B 树相对平衡二叉树最大的变化是：节点更大、层数更少。
当用于数据库索引时，它能很好利用磁盘块读取特性：
  • 一次 I/O 会把一个块读入内存。
  • 节点能装下更多 key，就能让同一次 I/O 带来更多“可比较的信息”。
  • 树高度下降，查找路径变短，I/O 次数下降。
如果把二叉树比作“爬高楼找房间”，那 B 树更像“坐电梯到几层，再在这一层里找门牌号”。电梯次数（I/O）少，体验就更丝滑。

B+ 树（B+Tree）

B+ 树是对 B 树在数据库场景下的主流改造。
B+树

一个直观的理解

  • 内部节点更像“纯索引”，只负责导航。
  • 数据（或数据指针）集中在叶子节点。
  • 叶子节点用链表串起来，天然支持范围扫描。
📌
数据库为什么更爱 B+ 树？
因为它把“范围查询”和“顺序扫描”变得非常自然，而且查询路径更稳定。

B 树与 B+ 树的区别

对比项
B 树
数据指针分布
内部节点与叶子节点都可能存数据指针
key 是否重复
通常不重复
叶子节点组织
通常不强制链表结构
查询稳定性
命中位置不固定，可能在内部节点提前结束

B+ 树的优势（更贴近工程）

  • 更少 I/O：内部节点更小、更“密”，同一块能塞更多 key，树更矮。
  • 范围查询更强：叶子链表一拉，就可以顺序扫。
  • 更稳定的延迟：大多数查询都到叶子结束，性能波动更小。

B+ 树的增删改查（CRUD）

这一节把 B+ 树当作“数据库索引的数据结构”来理解。
🧭
记住两条就够用：
  • 内部节点只负责导航（更像目录）。
  • 叶子节点存数据指针，并且叶子之间有链表（更像排好序的书页）。

1）查（Read / Search）

  • 从根节点开始，在节点内部对 key 做定位（可视为二分或多分查找）。
  • 选择对应子指针一路向下。
  • 最终一定落到叶子节点。
  • 等值查询：在叶子上命中 key。
  • 范围查询：先定位到起点叶子，再沿叶子链表顺序扫描。

2）增（Create / Insert）

  • 找到应插入的目标叶子节点。
  • 把 key 插入并保持有序。
  • 如果叶子节点溢出（超过容量）：
    • 分裂叶子节点为两个叶子。
    • 把“分裂后的分隔 key”插入父节点（内部节点只放导航 key）。
    • 若父节点也溢出，继续向上递归分裂。
💡
B+ 树分裂时的一个关键点：
叶子节点分裂后，叶子链表要重新连好。

3）改（Update）

更新要分两类：
  • 改索引列（比如把索引 key 从 10 改成 11）：
    • 本质是 Delete + Insert。
    • 因为 key 在有序结构里“换值”会破坏顺序。
  • 改非索引列（比如更新某行的其他字段）：
    • 索引结构一般不变。
    • 只更新叶子指针指向的数据（或数据页中的记录）。

4）删（Delete）

  • 在叶子节点找到目标 key 并删除。
  • 删除后若节点低于下限：
      1. 优先向兄弟节点借位（redistribution）。
      1. 借不到再 和兄弟节点合并（merge）。
  • 合并会导致父节点需要删除或调整对应的分隔 key，可能一路向上递归。

B+ 树的代价

  • key 可能重复，占用空间略多。
但在数据库里，这点空间通常换来的是“性能稳定 + 范围查询舒服”，非常值。

B* 树（B- 树）

很多同学会把 B-Tree（B 树） 误写成 “B- 树”。这里我新增这一节，专门讲另一种经常被写作 B- 树 的变体：B* 树（B-star tree）。
⚠️
名词澄清：
  • B-tree：就是本文前面讲的 B 树。
  • B* tree（B-star tree）：很多中文资料会口语化地叫它“B- 树”，但严格说应写作 B* 树。

B* 树想解决什么问题

B 树在插入时，节点满了就会分裂。普通 B 树分裂时，通常会把一个满节点分裂成两个节点，并把中间 key 提升到父节点。
B* 树的目标是：
  • 让节点利用率更高（更少空洞）。
  • 减少分裂带来的额外 I/O 与结构变动。

核心改动：先“借位/重分配”，不行再“三分裂”

B* 树在节点即将溢出时，一般会优先尝试：
  1. 和相邻兄弟节点做重分配（redistribution）：
      • 如果兄弟节点还有空间，就把一部分 key 挪过去。
      • 同时调整父节点中的分隔 key，保证有序性。
  1. 如果兄弟也满了，再采用更“细腻”的分裂方式：
      • 把两个节点 + 父节点的一个分隔 key，重新分配到三个节点里（常见描述为 2→3 的分裂）。
🧠
直观感受：
B 树像“一个箱子满了就一刀切成两个箱子”；B* 树像“先看看隔壁箱子有没有空位能匀一匀，实在不行再更精细地拆成三个箱子”。

它带来的收益与代价

收益：
  • 节点更满，空间利用率更好。
  • 树在同样数据量下可能更矮，查询 I/O 更少。
代价：
  • 插入时的逻辑更复杂，重分配/三分裂需要更多调整。
  • 实现复杂度更高，所以你在主流数据库里不一定直接“看到”这个名字，但其思想在很多存储结构的优化里会出现。

什么时候会遇到它

  • 数据结构教材或论文里讨论“提高 B 树节点利用率”的章节。
  • 一些文件系统、存储引擎、索引结构的实现/改进方案（视具体系统而定）。

B* 树的增删改查（CRUD）

把 B* 树当作“更在意节点利用率的 B 树变体”来理解，它的 CRUD 和 B 树非常像，区别主要体现在 插入/删除的再平衡策略。
🧩
一句话：
  • 查：和 B 树一样走索引路径。
  • 增/删：优先和兄弟节点 重分配，不行再做更“精细”的结构调整（常见 2→3 分裂）。

1）查（Read / Search）

  • 查找路径与 B 树一致：从根向下定位区间，直到命中 key 或到叶子。
  • 复杂度依旧是对数级别（取决于树高）。

2）增（Create / Insert）

  • 先定位到目标叶子/目标节点，把 key 按序插入。
  • 若节点未溢出：结束。
  • 若节点将溢出：B* 树通常按下面顺序处理：
      1. 优先重分配（redistribution）：
          • 看左右兄弟是否有空位。
          • 有空位就把一部分 key 在兄弟间挪动，同时更新父节点分隔 key。
      1. 兄弟也满了才分裂：
          • 常见做法是把“当前节点 + 兄弟节点 + 父节点一个分隔 key”一起重新分配，形成 3 个节点（2→3 分裂）。
📈
为什么这能提升利用率？
因为它尽量避免“一满就一刀切”，而是先把空间用满、用匀。

3）改（Update）

同 B 树 / B+ 树一样，更新分两类：
  • 改索引 key：本质是 Delete + Insert（因为要保持有序）。
  • 改非索引数据：索引结构通常不变，只更新记录内容。

4）删（Delete）

  • 定位并删除目标 key。
  • 若节点低于下限：
      1. 优先重分配：从兄弟节点借 key 并调整父节点分隔 key。
      1. 借不到再 合并/再分配结构：
          • 与兄弟合并会导致父节点减少一个分隔 key。
          • 可能递归向上处理，直到满足约束或根节点收缩。

B 树、B+ 树、B* 树的实际应用

这一节不讲抽象定义，直接把它们放回真实系统里看：当你在数据库里建索引、做范围查询、做排序分页时，底层就是这套思路。
🏗️
结论先行：
  • 数据库索引几乎都是 B+ 树（或以 B+ 树为核心思想的变体）。
  • B 树更多是“概念基础”或少数特定实现会用，但在主流关系型数据库里并不常见。

1）关系型数据库索引：PostgreSQL 的 B-tree vs 其他系统的 B+ 树

先纠正一个容易混的点：
  • PostgreSQL 默认的 B-tree 索引实现是 B-tree 家族（不是典型意义上的 B+ 树）。
  • MySQL InnoDB、Oracle 更常被描述为使用 B+ 树（或非常接近 B+ 树的实现）。
即便实现细节不同，它们在工程上想解决的问题非常一致：把树做得“更矮更宽”，减少磁盘 I/O。
在范围查询、排序分页这些高频场景下，B+ 树之所以常见，原因主要有三点：
  • 范围查询多：WHERE a BETWEEN 10 AND 20、a > 10 这类查询太常见，叶子链表让顺序扫描非常顺。
  • 排序分页多：ORDER BY a LIMIT 100 OFFSET 100000 本质是沿着有序叶子往后走。
  • 更稳定的性能：查询基本都会到叶子节点，路径长度更一致。
你可以把 B+ 树想象成“目录 + 连续页码的书页”：目录负责定位起点，书页之间是连着的。

2）点查（等值查询） vs 范围查（区间查询）

🔎
点查（=）：更关心“最快定位到某个 key”。
范围查（>、<、BETWEEN）：更关心“找到起点后能不能顺滑地往后扫”。
  • 对点查来说，B 树和 B+ 树都能做到对数级查找。
  • 对范围查来说，B+ 树几乎天然占优：找到起点后沿叶子链表遍历即可。

3）聚簇索引与二级索引（以 InnoDB 为例）

在 InnoDB：
  • 聚簇索引（Clustered Index）：主键索引的叶子节点存的是“整行数据”。
  • 二级索引（Secondary Index）：叶子节点存的是“二级索引 key + 主键值”，再回表到聚簇索引取完整行。
这就是你会听到的经典优化建议来源：
  • 能用覆盖索引就用覆盖索引（减少回表）。
  • 主键尽量自增或递增（减少页分裂，写入更友好）。

4）写多还是读多：分裂/合并在工程里的意义

  • 写入压力大时（大量 INSERT/UPDATE）：
    • 节点分裂更频繁。
    • 随机主键会导致页分裂和碎片更明显。
  • 读为主时：
    • B+ 树的“叶子链表 + 更密的内部节点”通常带来更好的吞吐。
⚖️
工程视角的 trade-off：
B+ 树为了读（尤其范围读）更顺，会付出一些维护结构的写入成本。

5）什么时候更可能听到/用到 B 树

虽然数据库索引常用 B+ 树，但 B 树并不是“没用”，它更像是：
  • 学习多路平衡树的基础模型。
  • 在一些存储系统或特定实现中，可能会用“B 树思想”的结构（实现细节各家不同）。

结尾

把这篇文章收束成一张心智地图，可以是这样：
🗺️
同一个目标：更少 I/O。
  • B 树：多路 + 平衡，让树“更矮更宽”，用更少层级换更少 I/O。
  • B+ 树：把数据（或数据指针）集中到叶子，并把叶子串起来，让范围查询、排序、顺序扫描更丝滑。
  • B* 树：在插入/删除再平衡上更“精打细算”，优先重分配，必要时 2→3 分裂，追求更高的节点利用率。
如果只记一句话：索引结构的胜负，不在“树长什么样”，而在“磁盘要读几次”。
当你下次写出 WHERE ... BETWEEN ...、ORDER BY ... LIMIT ...，或在索引列上做大量写入时，可以把它们映射回本文的 CRUD：
  • 读：尽量一次定位 + 顺序扫
  • 写：尽量少分裂、少回表、少随机 I/O
这也是为什么数据库世界里，B-tree 家族会长期成为默认答案。

参考

  • 《数据结构（严蔚敏）》相关章节
  • 《数据库系统概念（Database System Concepts）》索引与 B+ 树章节
  • 维基百科：B-tree、B+ tree
Loading...