(b2)B-树：结构
看清每个节点的装填规则、分裂时机与高度控制
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
(b2)B-树：结构
看清每个节点的装填规则、分裂时机与高度控制
观察体验
前面我们从整体认识了 B-树的结构。现在换个角度——先不看定义，直接盯着一棵实例：每个节点装多个键，所有叶子齐刷刷落在同一层。
字典按字母分成多区，区间边界就是键，每区背后是一组词条（子树）
多路平衡
上页看到，每个节点能装多个 key、分多个分支，整棵树高度却被压得极低。这背后靠的就是 B-树最核心的结构性质——多路平衡。
一个经理直接管 m 个下属，下属再各管 m 个——扇出大、层级少，且每条汇报路径同级
还是I/O
上一页我们说 B-树『多路』又『平衡』——可你可能想问：为什么非得这么设计？答案很朴素：一切为了 I/O。
找一本书时，你搬的是整箱书（页），而不是一页一页翻（key）
深度统一
上一页从磁盘I/O的角度看B-树，发现一个隐患：不同查找走过的层数如果不一样，磁盘读取次数就不可预测。B-树用一条铁律解决这个问题——所有叶子节点必须位于同一深度。
任意房间从大堂出发要坐的楼层数都一样，对应任意查找的磁盘读取次数都一致
阶次含义
上一页我们让节点尽量多装关键字以摊薄 I/O，可「最多装多少」必须有个数——这就是「阶 m」。麻烦的是：业界对 m 的定义不统一，相同数字背后其实差着将近一倍。
同样叫 L，各品牌大小各异；同样叫 m 阶，不同教材差近一倍——必须先问「按谁的定义」
: 紧凑表示
上页说清了一棵 B-树节点的『阶』由几个键决定。但要把整棵树存到磁盘，光有节点还不够——键和指针该怎么排？紧凑表示给出了一个极端答案：把一切摊平。
不再分『每班一页』，所有人排成一列；想找某班同学，要靠额外记下的学号边界
BTNode
上一页把多个键塞进一个连续空间——那就是一个 B-树节点。现在打开它，看里面到底装了什么。
容量固定，满了换新抽屉或拆分；抽屉间按编号范围相连
BTree
前面几页我们分别看了节点能装多键、树高统一、阶次含义等特征，但这些还像散落的零件。现在用一句话把它们拢成 B-树的正式定义。
节点必须正好装入一页——太少浪费 I/O 带宽，太多装不下就必须分裂
本节要点
- ✓多路摊薄I/O，深度统一是B-树的命脉
- ✓节点子树数在⌈m/2⌉到m之间，根是唯一例外
- ✓紧凑表示把多指针结构压成线性数组，遍历更友好
- ✓BTree管分裂合并路由，BTNode管单节点存取
课后思考
三个开放问题，先独立思考再看参考答案，每题都值得在纸上画一画。
参考答案下界若为 1，单孩子节点会拉长路径，树退化为细高形，深度趋近元素数，I/O 暴涨。⌈m/2⌉ 把树钉死在「胖矮」区间，保证深度为 O(log_m N)。
参考答案应让 m 尽量大，使节点刚好填满一页。m↑→树高↓→查询 I/O 次数↓，但单页 I/O 数据量↑，节点内维护（分裂/合并）代价也↑。这是阶次选择的核心权衡。
参考答案查找正确性只依赖「路径长度统一」，与节点是否下溢无关，所以查找仍正确。但删除无法收敛——总有节点欠债，结构长期失衡。破坏的是「写后不变形」的不变量。