7.4.2 B+ 树的基本概念
原书定位
印刷页P314起,对应PDF第326页。下文为目视整理的知识提要;完整内容见原书对照。
按本书定义, 阶 B+ 树每个分支最多 个孩子,分支关键字数与孩子数相同,关键字保存各孩子子树的最大值;其他定义可能用最小值或分隔键,手算按题设。
全部记录关键字和记录指针在叶层,有序叶结点由链相连。分支仅作索引,其关键字也会出现在叶层;精确查找即使在分支命中也需继续到叶层,范围查询可沿叶链顺序扫描。
与 B 树相比,分支不存完整记录地址可提高每块分支数,减少高度;叶链支持顺序查找。B 树的关键字通常只在某一个实际结点出现,成功可在中途停止。

B+ 树索引层与叶链,原书P314。
对应练习
关联知识
原书对照
展开原书对照截图

