考研笔记

B+树的基本概念

大纲对这一节只要求「了解基本概念和性质」，不要求操作过程。 所以这一页的重心不是插入删除，而是五条定义和与 B 树 的五点差异——考的几乎全是对照题。

教材给的定位是一句话：B+树是应数据库所需而出现的一种 B 树的变形树。

「应数据库所需」是理解全节的钥匙。数据库要的不只是「按主键查一条」，还要「按主键范围扫一批」。B 树能做第一件事，做第二件事要不停地在树上上上下下；B+树把所有数据压到叶子层并串成链表，范围扫描就退化成沿链表走一遍。这一个改动带出了其余所有差异。

机制

五条定义

一棵 阶 B+树应满足下列条件：

  1. 每个分支结点最多有 棵子树（孩子结点）。
  2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 棵子树。
  3. 结点的子树个数与关键字个数相等。
  4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）。
  5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（下一级的索引块）中关键字的最大值及指向其子结点的指针。

边界辨析：

条件 3 是 B+树与 B 树最根本的一条差异，其余四条都是它的后果。 B 树里关键字是「隔板」，所以子树比关键字多一个； B+树里每个关键字就是它那棵子树的代表（最大值），所以一一对应。 记住这一条，第 1、2 条里那些看起来和 B 树一样的数字，含义其实全变了。

flowchart TD
    R["60    85"]
    R --- A["10   20   50   60"]
    R --- B["77   85"]
    A --- L1["8   10"]
    A --- L2["16   20"]
    A --- L3["40   50"]
    A --- L4["55   60"]
    B --- L5["69   77"]
    B --- L6["80   85"]
    L1 -.->|"链表"| L2 -.-> L3 -.-> L4 -.-> L5 -.-> L6
    H1(["头指针 1<br/>→ 根结点"]) --> R
    H2(["头指针 2<br/>→ 最小关键字叶结点"]) --> L1

    classDef idx fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef leaf fill:#c8e6c9,stroke:#1b5e20,stroke-width:2px
    classDef ptr fill:#fff9c4,stroke:#f57f17
    class R,A,B idx
    class L1,L2,L3,L4,L5,L6 leaf
    class H1,H2 ptr

分支结点的关键字是其子树中最大关键字的副本。 根结点的 60 是左子树里最大的，85 是右子树里最大的；10 20 50 60 这四个数分别是它四个孩子的最大值。所以 60 和 85 各出现了两次——在 B 树里这是不可能的。

通常在 B+树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此可以对 B+树进行两种查找运算：

入口查找方式用途
头指针 → 最小关键字叶结点顺序查找（沿叶结点链表）范围扫描、全表遍历
头指针 → 根结点多路查找（自顶向下）单点定位

与 B 树的五点差异

#B+树B 树
1具有 个关键字的结点只含 棵子树，每个关键字对应一棵子树具有 个关键字的结点含 棵子树
2非根内部结点关键字数 ；非叶根结点 非根内部结点 ；根结点
3叶结点包含全部关键字，非叶结点中出现的关键字也会出现在叶结点中最外层终端结点包含的关键字和其他结点包含的关键字不重复
4叶结点包含信息；所有非叶结点仅起索引作用，索引项只含对应子树的最大关键字和指针，不含记录的存储地址每个结点都含有对应记录的存储地址
5用一个指针指向关键字最小的叶结点，将所有叶结点串成一个线性链表无叶结点链表

差异 2 的数字要一起记，不要单记一边。 B+树的关键字数范围整体比 B 树「向右挪了一格」，正是因为差异 1——同样的子树数，B+树的关键字要多一个。

差异 4 的收益要能说出来：非叶结点不含记录地址，这样能使一个磁盘块存储更多的关键字，使得磁盘读/写次数更少，查找速度更快。这是 B+树在数据库里胜过 B 树的直接原因。

关联对照：

由差异 4 可以推出一条常考的性质：B+树的查找无论成功与否，都必须走到叶结点。 因为非叶结点里的关键字只是「副本」，不带记录地址——在分支结点上撞到相等的值也不算找到。 B 树则相反，可能在任意一层就查找成功。 两句话是一组，要一起答。

边界

说法判断说明
「B+树是 B 树的一种」⚠️教材措辞是「B 树的变形树」，不是子集
「B+树中关键字数 = 子树数 − 1」❌相等。这是与 B 树最根本的差异
「B+树非根内部结点关键字数是 到 」❌那是 B 树。B+树是 到
「B+树的非叶结点存记录地址」❌仅起索引作用，只含最大关键字和子树指针
「B+树的关键字不重复出现」❌非叶结点的关键字是叶结点关键字的副本，必然重复
「B+树查找可能在分支结点上成功」❌一定要走到叶结点
「B 树查找一定要走到最底层」❌B 树可能在任意层成功
「B+树只有一个头指针」❌两个：指向根、指向最小关键字叶结点
「B+树的叶结点也相互链接是为了方便插入」❌是为了支持顺序查找 / 范围扫描
「分支结点存的是子树的最小关键字」❌教材口径是最大值

口径差异：

「分支结点存子树的最大关键字」是王道 / 国内教材的口径。 数据库教材和工程实现（MySQL InnoDB 等）里常见的是「存子树的最小关键字」， 叶结点也常常只挂数据而由分隔键索引。两种画法都能自洽，但答题必须按王道的最大值口径， 否则整棵树的关键字副本位置全都对不上。这是有工程/竞赛背景的人在这一节唯一会踩的坑。

对照速查

B 树B+树
关键字与子树子树 关键字 子树 关键字
非根内部结点关键字数
根结点关键字数（非叶根）
关键字是否重复不重复重复（副本）
记录存在哪各层结点只在叶结点
查找终点可能在任意层必到叶结点
叶结点链表无有
头指针1 个2 个
典型场景文件索引数据库索引、范围查询

考点

  • 五条定义，尤其「子树个数与关键字个数相等」。
  • 与 B 树的五点差异（2016 命题追踪，几乎年年以选择题出现）。
  • B+树查找必到叶结点，B 树可在任意层成功。
  • 非叶结点不含记录地址 → 一个磁盘块能装更多关键字 → I/O 更少。
  • 两个头指针、两种查找运算。
  • B+树的应用场合（2017 命题追踪）：数据库索引、需要范围查询的场合。

链接

反向链接