7.4.2 B+ 树的基本概念

教材导航 · 第7章

原书定位

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

按本书定义,mm 阶 B+ 树每个分支最多 mm 个孩子,分支关键字数与孩子数相同,关键字保存各孩子子树的最大值;其他定义可能用最小值或分隔键,手算按题设。

全部记录关键字和记录指针在叶层,有序叶结点由链相连。分支仅作索引,其关键字也会出现在叶层;精确查找即使在分支命中也需继续到叶层,范围查询可沿叶链顺序扫描。

与 B 树相比,分支不存完整记录地址可提高每块分支数,减少高度;叶链支持顺序查找。B 树的关键字通常只在某一个实际结点出现,成功可在中途停止。

B+ 树索引层与叶链

B+ 树索引层与叶链,原书P314。

对应练习

7.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P314,PDF第326页

原书对照,原书P315,PDF第327页