【喝前摇一摇】B树与B+树

Serena 203 次阅读 发布于 2026-07-09 学习心得

本系列主要写一些只需要考前记一记的知识点，供自己使用，时间有限不保证可读性

B树

B树的特征

①除根结点外，每个结点的分叉数不少于⌈m2⌉\lceil\frac{m}{2}\rceil（一般m阶表示有m个分叉的意思）

②平衡——每棵子树的高度都相同

③叶子结点不带有关键字与信息（被称为失败结点，叶子结点的父结点被称为终端结点）

④非叶结点的结构： nP0K1P1⋯KnPn\begin{array}{|c|c|c|c|c|c|c|} \hline \;n & P_0 & K_1 & P_1 & \cdots & K_n & P_n \\ \hline \end{array}

特性1：P0所指子树关键字<k1<P1所指子树关键字<⋯<kn<Pn所指子树关键字P_0所指子树关键字<k_1<P_1所指子树关键字<\cdots<k_n<P_n所指子树关键字

特性2：关键字数量始终比分叉数（阶数）少1

一棵n个结点的m阶B树的高度范围：

logm(n+1)≤h≤log⌈m2⌉n+12+1 log_m(n+1) \le h \le log_{\lceil\frac{m}{2}\rceil}\frac{n+1}{2}+1

B树的插入（以5阶B树为例）

5阶B树一个结点可以容纳⌈m2⌉−1≤k≤m−1\lceil\frac{m}{2}\rceil -1 \le k \le m-1个关键字（根结点无下限），即2≤k≤42 \le k \le 4

当插入操作导致关键字超过这个结点的上限后，需要将该结点分裂。

①对于根结点：将⌈m2⌉=2（从0开始数）\lceil\frac{m}{2}\rceil = 2（从0开始数）处的关键字提出，加入新的根结点

②对于非根结点：同样将⌈m2⌉\lceil\frac{m}{2}\rceil处的关键字提出，并将其塞入父结点，若父结点也满了就重复这两个操作直至所有结点的关键字数量都符合要求

B树的删除

对于非终端结点：删除一个关键字通常删除他的前驱或者后继的关键字，转换为删除终端结点的关键字

对于终端结点：当删除操作不会导致关键字个数不低于下限时，直接删除；若低于下限则有以下3个方法：

①后继前移：右兄弟关键词冗余，将后继和后继的后继前移

②前驱后移：左兄弟关键词有冗余，将前驱和前驱的前驱后移

③结点合并：左、右兄弟关键词均已达到下限，进行结点合并，将父结点中的关键词提出，将两个结点合并为一个结点，若父结点此时关键词达到下限，重复操作

B+树

B+树特征（不考插入删除）

①阶数为m的B+树最大分叉数和结点数均为m

②非叶根结点（不是叶子的根结点，即树高大于1时）至少有2棵子树（为了保持平衡），其他结点不少于⌈m2⌉\lceil\frac{m}{2}\rceil棵

③叶子结点即为有效结点，包含全部关键字及指向记录的指针

⑤叶结点按照关键字大小排序，相邻的结点互相链接（支持顺序查找）

⑥其他分支结点仅包含子结点中的最大值

B树与B+树对比

B树B+树
结点中关键字个数
与子树数量（分叉数量）		k个关键字对应k+1棵子树k个关键字对应k棵子树
m阶树的结点关键字个数范围根：k∈[1,m−1]k\in [ 1,m-1 ]
非根：k∈[⌈m2⌉−1,m−1]k\in [ \lceil \frac{m}{2} \rceil -1,m-1 ]		根：k∈[1,m]k\in [ 1,m]
非根：k∈[⌈m2⌉,m]k\in [ \lceil \frac{m}{2} \rceil, m]
结点信息关键字不重复，结点中包含全部信息非叶结点仅为索引，不包含全部信息；叶结点包含全部信息

相同点：除了根结点外都需要有⌈m2⌉\lceil \frac{m}{2} \rceil棵子树，且子树高度必须相同（平衡）

拓展

Q：如何理解B+树可使得一个磁盘块可包含更多关键字，使得B+树阶数更大，树高更矮，读磁盘次数更少？

A：这题好像有点超纲

一般一个磁盘块大小对应一个结点。查询时，无论B树还是B+树，都是把整个结点（一整个磁盘块）一次性读入主存。

B树的每个关键字都要附带一个记录指针（指向对应的数据），再加上子树指针，一个结点要存三类信息；而B+树的内部结点只存关键字和子树指针，记录指针全部放在叶子结点里，内部结点不存数据地址。

因此在同样大小的磁盘块里，B+树内部结点能放下更多关键字 → 阶数更大 → 同样数据量下树高更矮 → 查询时需要的磁盘I/O次数更少。