7.4.1 B 树的定义
原书定位
印刷页P311起,对应PDF第323页。下文为目视整理的知识提要;完整内容见原书对照。
阶 B 树每个结点最多 个孩子、 个关键字。非根实际结点至少 个关键字;非空根至少 1 个关键字,非终端根至少两个孩子。
含 个关键字的内部结点有 个子树位置,关键字有序,子树中的所有关键字落在相邻分隔值界定的区间内。所有空的外部失败结点在同层。
**名词约定:**教材把空外部失败结点称“叶结点”,高度不含这一层;部分真题把最底层存关键字的实际结点称“叶结点”。下文称后者为终端实际结点,计算前先对齐口径。

五阶 B 树与外部失败结点,原书P311。
下级知识点
对应练习
关联知识
- 7.3.3.1 红黑树的插入
- 7.3.3.2 红黑树的删除
- 7.4 B 树和 B+ 树
- 7.4.1.1 B 树的查找
- 7.4.1.2 B 树的高度
- 7.4.1.3 B 树的插入
- 7.4.1.4 B 树的删除
- 7.4.2 B+ 树的基本概念
- 8.7.1 外部排序的基本概念
原书对照
展开原书对照截图
