(b3)B-树：查找

官官方信息技术老师·13 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ (b3)B-树：查找信息技术(b3)B-树：查找算法过程
B-树查找数据结构算法

B-树的查找

搞懂B-树查找全流程：路径选择、命中判断与各种边界情形

按 空格/→ 演示下一步

1 / 13 页

全部页面点击任意一页，跳回舞台从这页播放

B-树查找数据结构算法

B-树的查找

搞懂B-树查找全流程：路径选择、命中判断与各种边界情形

1第 1 页 · B-树的查找

B-树的关键特征

上次查找我们沿着指针一路跳，每跳一步都要在节点内做一次有序比较。现在反过来看：节点里关键字数量有规定吗？B-树的硬约束——根的特判、关键字上下界、节点内部结构——就写在这一层。

根节点特判
非叶根至少 2 棵子树；整棵树只有根一个节点时，可只含 1 个关键字
关键字上界
m 阶 B-树的每个节点至多含 m-1 个关键字
关键字下界
除根外，非叶节点至少含 ⌈m/2⌉-1 个关键字，防止树偏向一侧
节点内部结构
n 个关键字与 n+1 个指针交错，把子树分成 n+1 段
字典检字表对应 →B-树节点

n 个检字把字典划成 n+1 段，节点内关键字也按序切分子树

⌈m/2⌉−1≤n≤m−1\lceil m/2 \rceil - 1 \leq n \leq m - 1
2第 2 页 · B-树的关键特征

m阶B-树的定义

上页说到 B-树「多路平衡、有序分裂」。但一个节点到底最多能分几路、装几个关键字？这就要先约定一个数——阶数 m。这一页把 m 给节点的硬约束讲清楚。

阶数 m 的定义
规定每个节点最多 m 个子节点、对应最多 m-1 个关键字
非根节点范围
子节点数 ∈ [⌈m/2⌉, m]；关键字数 ∈ [⌈m/2⌉-1, m-1]
根节点例外
内部节点时至少 2 个子节点；叶子根可无子节点
k 键 ⇔ k+1 子
节点含 k 个关键字必有 k+1 个子节点；根除外
公司管理层对应 →m 阶 B-树

管理者最多管 m 个下属对应节点最多 m 子节点；非 CEO 至少管 ⌈m/2⌉ 人对应非根下限

child∈[⌈m/2⌉, m],key∈[⌈m/2⌉−1, m−1]\text{child} \in [\lceil m/2 \rceil,\ m],\quad \text{key} \in [\lceil m/2 \rceil - 1,\ m-1]
3第 3 页 · m阶B-树的定义

查找算法的过程

把节点内二分与节点间下降两种搜索叠加起来，就是B-树的完整查找过程。

1
从根节点出发
入口唯一，所有查找从根开始，保证对数级路径长度
2
节点内二分查找
节点内关键字有序，用二分定位候选区间
3
比较判定分支
命中则结束，否则落在某区间决定走哪个子节点
4
沿子指针下降
选中子节点成为新当前节点，再做一次二分
5
叶节点未命中即失败
到叶仍未找到，查找终止返回失败
4第 4 页 · 查找算法的过程

查找操作实例

绿色节点依次亮起，展示指针从根下移、每层二分、直到命中或在叶子层失败的完整过程。

图解渲染中…
s3：在当前节点的有序关键字序列上做二分s6：判断当前节点是否为叶子节点s8：依 k 与 k_i 的大小定位子树区间s11：指针下移到子节点后回到节点内二分
5第 5 页 · 查找操作实例

查找算法的实现

cpp

B-树查找核心代码：节点内顺序扫描定位 + 子树递归下降

代码高亮加载中…

i 从 0 顺序扫描定位；命中返回当前节点，未命中若为叶子则失败，否则沿 children[i] 递归下降——B-树自顶向下查找的标准范式。

6第 6 页 · 查找算法的实现

主成本：I/O次数

B-树是为磁盘而生的数据结构。磁盘读写以"块"为单位，而 B-树的每个节点恰好对齐一个磁盘块。所以查找时从根到叶，每经过一个节点就是一次磁盘 I/O——路径长度就是 I/O 次数。

节点对齐磁盘块
每个节点大小与磁盘块相等，读一个节点就是一次 I/O
查找走单一路径
节点内二分定位后只选一个子树下降，不回溯不分叉
I/O 次数等于树高
根到叶路径上每个节点各一次 I/O，总共 h 次
节点内查找近免费
块内关键字比较是内存操作，相对 I/O 可忽略
翻字典找词对应 →B-树逐层定位

字典按目录→部首→页码逐层缩窄，每次翻页对应一次 I/O

h≈log⁡mnh \approx \log_m n
7第 7 页 · 主成本：I/O次数

次成本：节点内查找

上页我们算了主成本：树高 h 次磁盘 I/O。但节点读进内存后，里面有 m-1 个键，还得再找——这就是次成本：从磁盘读到的这块数据里「翻到」目标键。

节点内容
一个节点最多存 m-1 个有序键，读入内存后要在其中定位
二分查找
键在节点内有序排列，用二分在 O(log m) 步内定位
CPU 比较代价
每次比较是 CPU 指令，量级远低于一次磁盘 I/O
主次成本合并
总成本 ≈ h×I/O + h×log₂m×比较，I/O 才是大头
查字典对应 →节点内二分查找

字典按字母排好，先翻到大概页码再确认，对应有序键的二分定位

T=h⋅(tio+⌈log⁡2m⌉⋅tcmp)T = h \cdot (t_{io} + \lceil \log_2 m \rceil \cdot t_{cmp})
8第 8 页 · 次成本：节点内查找

最小高度

上一页讲 I/O 次数等于树高，那最理想的情况——只查一次就能找到——树得多矮？答案是所有节点都饱和的时候。

饱和节点
每个内部节点塞满 m 个孩子、m-1 个键
满树容量
第 h 层共 m^(h-1) 个节点，整树键数 ≤ m^h - 1
最小高度
h_min = ⌈log_m(N+1)⌉，再满也压不到更矮
I/O 下界
等于树高，是查找最优情况下要走的层数
公司每个部门满编对应 →节点饱和的 B-树

部门满员意味着管理跨度最大，公司层级自然最少

hmin⁡=⌈log⁡m(N+1)⌉h_{\min} = \lceil \log_m (N+1) \rceil
9第 9 页 · 最小高度

最大高度

上一页我们看了 B-树最小高度——每个节点都尽量多装关键字。这次反过来，如果每个节点都只装到最低下限，存同样多的关键字，树会被"拉"到多高？

最瘦的结构
每个内部节点只取最小孩子数，让整棵树向纵深生长
根的特例
根至少 2 个孩子（除非是叶子），其他内部节点至少 ⌈m/2⌉ 个
节点逐层翻倍
从根往下每层节点数乘以 ⌈m/2⌉，叶子层汇聚全部 N 个关键字
最大高度上界
几何累加后反推，得出 h 的上界公式
公司层级对应 →B-树最大高度

经理带最少下属对应节点取最小孩子数，员工总数对应关键字总数

h≤1+log⁡⌈m/2⌉N+12h \leq 1 + \log_{\lceil m/2 \rceil} \frac{N+1}{2}
10第 10 页 · 最大高度

高度公式对比

最小与最大高度公式的对照总结

高度公式对比
最小与最大高度公式的对照总结
11第 11 页 · 高度公式对比

B-树查找总结

  • ✓查找路径等于树高，每层触发一次磁盘读
  • ✓主成本是磁盘I/O，节点内开销可忽略
  • ✓阶数m越大树越矮，但单节点会变胖变慢
  • ✓最坏高度即查询最坏磁盘访问次数
延伸主题：B-树的插入与节点分裂B+树：所有数据落在叶子层磁盘页大小与缓冲池管理
12第 12 页 · B-树查找总结

课后思考

先自己琢磨，再对照参考答案看思路差在哪。

1B-树节点内部查找为何不直接用二分？节点大小受什么硬约束？

参考答案节点内关键字数常远小于百个，顺序遍历已够；二分节省被额外比较和分支预测失效抵消。节点大小由磁盘页对齐决定。

2若全部节点驻留内存，B-树的查找成本模型和相对优势会怎么变？

参考答案主成本 I/O 消失，只剩 CPU 比较；B-树常数因子在内存下不再划算，红黑树等结构反而占优。

3B+树把所有数据挪到叶子层，这对查找终止位置和范围查询有什么影响？

参考答案B+树查找必到叶子才终止；范围查询可直接在叶子链表顺序扫描，省去回溯上层的过程。

13第 13 页 · 课后思考