在线 -
搜索 AIGC编程网
← 返回题目列表

B 树、B+ 树、B* 树有什么区别？

高频 中等 第 7 / 25 题 更新于 2026/08/03
B树B+树B星树对比

简化版

它们是同一个家族、层层改进：B 树——多路平衡树，每个节点都存数据；B+ 树——数据全下沉到叶子、内部只存索引、叶子连成有序链表（更适合磁盘索引和范围查询）；B* 树——在 B+ 树基础上，给内部节点也加了指向兄弟的指针，节点满时先尝试向兄弟「挪」而不是急着分裂，把空间利用率下限从 1/2 提高到 2/3。

详细版

特性B 树B+ 树B* 树
数据存放所有节点只在叶子只在叶子（同 B+）
内部节点存关键字+数据只存关键字（索引）只存关键字（索引）
叶子链表无有（有序链表）有
兄弟指针无叶子间有内部节点间也有
分裂策略满则分裂满则分裂满时先向兄弟转移，两个都满才分裂
空间利用率下限~1/2~1/2~2/3
主要用途部分文件系统、早期数据库数据库索引主流（MySQL 等）部分文件系统（如早期 HFS）

完整版教学

一、B 树：家族起点

B 树是多路平衡查找树，核心是「大扇出、矮树、所有叶子同层」，为磁盘查找而生。它的特点是每个节点（包括内部节点）都存数据。这带来一个问题：内部节点存了数据就装不下太多关键字，扇出受限，且范围查询要在树里回溯。后续的 B+ 树就是冲着这两个痛点改的。

二、B+ 树：为索引和范围查询而改

B+ 树在 B 树基础上做三件事（详见 B+ 树专题）：

  1. 数据全下沉到叶子，内部节点只当「索引路标」→ 内部节点能装更多关键字 → 扇出更大、树更矮。
  2. 叶子连成有序链表 → 范围查询、排序只需顺着链表扫。
  3. 所有查询都走到叶子 → 延迟稳定。

这些改造让 B+ 树成为数据库索引的绝对主流（MySQL InnoDB、Oracle、PostgreSQL 索引等）。

三、B* 树：提高空间利用率

B* 树是 B+ 树的进一步优化，针对「节点分裂太频繁、空间利用率只有 50%」的问题。它的两个改动：

  1. 内部节点之间也加兄弟指针（B+ 树只有叶子间有）。
  2. 改变分裂策略：一个节点满了，不急着分裂，而是先看相邻兄弟有没有空位——有就把一部分关键字转移给兄弟（类似删除时的「借位」反向操作），避免分裂；只有当自己和兄弟都满了，才把两个满节点分裂成三个节点。

因为「两满分三」而不是「一满分二」，每个节点分裂后至少是 2/3 满，所以空间利用率下限从 1/2 提高到 2/3，节点更饱满、树更紧凑。

四、为什么数据库主流是 B+ 树而不是 B* 树

B* 树空间利用率更高，听起来更好，但数据库主流仍是 B+ 树，因为：

  • B* 树「向兄弟转移」的逻辑更复杂，插入删除时要协调兄弟节点，实现和并发控制更麻烦。
  • B+ 树已经足够矮、足够快，2/3 vs 1/2 的空间收益在实际中不足以抵消复杂度和维护成本的增加。

所以 B* 树多见于对空间利用率敏感的文件系统（如早期苹果 HFS），而数据库索引选了实现更简单、综合更优的 B+ 树。

五、一句话串起家族

  • B 树：多路矮树，节点都存数据。
  • B+ 树：数据下沉叶子 + 叶子链表，为索引和范围查询优化 → 数据库主流。
  • B* 树：B+ 树 + 内部兄弟指针 + 满时先转移再分裂 → 空间利用率更高，多用于文件系统。

六、常见误区与追问

考点正确口径
B 树内部和叶子都可存数据
B+ 树数据集中叶子，叶子链表支持范围查询
B* 树提高节点利用率，分裂前先和兄弟重分配
B: data in every node
B+: data only in leaves + linked leaves
B*: redistribute with sibling before split

B 树家族的差异，本质是在磁盘页利用率、查询稳定性和范围扫描之间取舍。

  • 误区：B 树、B+ 树、B 树只是名字不同。* 它们的数据存放位置、叶子链接和分裂策略都不同。
  • 误区：B 树一定比 B+ 树查找慢。 B 树可能在内部节点命中；但 B+ 树查询路径稳定、范围扫描更强。
  • 误区：B 树一定是数据库主流选择。* B* 树空间利用率高，但实现和维护更复杂，工程主流仍常见 B+ 树。
  • 追问：B+ 树为什么适合范围查询？ 所有数据在叶子层且叶子按 key 链接，定位起点后可顺序扫。
  • 追问：B 树如何提高利用率？* 分裂前优先和兄弟节点重分配，两个节点不够时再拆成三个节点。
  • 追问：如何快速区分三者？ B 树是多路查找基础，B+ 树强化索引和范围，B* 树强化页空间利用率。

七、加强记忆

B 树家族层层改进：B 树（多路平衡、每个节点都存数据）→ B+ 树（数据全在叶子、内部只存索引、叶子连有序链表，扇出大、范围快、延迟稳，数据库索引主流）→ B* 树（在 B+ 基础上给内部节点加兄弟指针、满时先向兄弟转移再分裂，空间利用率从 1/2 升到 2/3，多用于文件系统）。数据库选 B+ 树是因为它够快且实现更简单。