7.4.1 B 树的定义

教材导航 · 第7章

原书定位

印刷页P311起,对应PDF第323页。下文为目视整理的知识提要;完整内容见原书对照。

mm 阶 B 树每个结点最多 mm 个孩子、m−1m-1 个关键字。非根实际结点至少 ⌈m/2⌉−1\lceil m/2\rceil-1 个关键字;非空根至少 1 个关键字,非终端根至少两个孩子。

含 rr 个关键字的内部结点有 r+1r+1 个子树位置,关键字有序,子树中的所有关键字落在相邻分隔值界定的区间内。所有空的外部失败结点在同层。

**名词约定:**教材把空外部失败结点称“叶结点”,高度不含这一层;部分真题把最底层存关键字的实际结点称“叶结点”。下文称后者为终端实际结点,计算前先对齐口径。

五阶 B 树与外部失败结点

五阶 B 树与外部失败结点,原书P311。

下级知识点

对应练习

7.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P311,PDF第323页