B 树：一棵矮胖、永远平衡的树，成本按读页数计价

它是干嘛的。 表里有几亿行，数据在磁盘上按固定大小的页存。查一行只能花几次读页：全表扫付不起，索引本身也大到装不进内存。

三条结构性质（说的是数据库实际用的变体 B+ 树）。

有序——全局有序，不是大致有序。 每个节点内的键排好序，内层节点的分隔键把整个键空间切成区间：左子树的键全小于分隔键、右子树全大于。一趟中序遍历就是全表键从小到大的完整序列，任何一把键只有一个合法位置。有序是"能定位"的全部前提。

叶子互为链表。 每个叶子页带 prev/next 指针，所有叶子按键的顺序串成双向链表——是逻辑顺序，不必等于物理位置。范围查询只需下降一次到起始叶，然后顺链表横着读页，不用每个键都重新从根下降。InnoDB 的间隙锁、Next-Key 锁锁的正是这条链上的一段（见 isolation-levels）。这条链的磨损形态是碎片：用久了逻辑相邻的叶子物理上越离越远，范围扫的顺序读逐渐退化，重建索引是对症的药。

永远平衡。 不变式：所有叶子深度完全相同；除根外每个节点半满到全满之间（随机插入下平均填充率约 69%）。平衡不是靠定期修整维持的——没有 AVL 那种旋转。它是下面插入算法里生长规则的副产品：树只许从根部长高，于是没有任何一条枝能比别的枝长。

层数算术——"四层"的来历。 扇出 ≈ 页大小 /（键 + 指针）≈ 500（8KB 页）。容量随层数：1 层 500，2 层 25 万，3 层 1.25 亿，4 层 625 亿。没有任何规则把层数钉死在四层——长到第五层毫无障碍；四层只是现实表规模算出来的结果，再加上最上面几层常驻缓存，"四层深"体感往往只有一次真实磁盘读。真正被引擎钉死的是页大小（PG 8KB、InnoDB 16KB），层数是它的影子。

插入算法。 三条因果决定一切，每一步都是它们的组合。(1) 路由：分隔键是路牌——小了往左、大了往右，落点唯一。(2) 容量：节点 = 一个磁盘页，页大小固定，所以键数上限是物理、不是政策。满（= 上限）合法；要塞上限 +1 个键不行——这样的节点不可能作为一页存在，必须分裂。(3) 界碑：节点一分为二后，父节点需要一个新分隔键来区分两半——比我小去左、比我大去右，上升的必须正好是站在两半之间的那个键。上升逐层向上传，止于第一个有空位的祖先；顶到根、根还满，根就分裂、新根诞生——这是树长高的唯一方式，也正因如此所有叶子永远等深。

演示（缩小版：每节点最多 3 个键；真实扇出几百，规则不变）。插 1、2、3 → 根 [1,2,3]：满了，但满合法，什么都不发生。插 4 → 根要装 4 个键：溢出。分裂成 [1,2] 和 [4]，界碑 3 上升进一个新根 [3]。树高变 2——经根长高，符合规则。插 5、6 → 按路牌（>3）落右叶，[4,5,6]。插 7 → 该叶要装 [4,5,6,7]：分裂成 [4,5] 和 [7]，界碑 6 上升进根；根有空位（1→2 个键），级联就此停住：根 [3,6]，叶子 [1,2] [4,5] [7]，叶链指针重新缝合。插 8、9 → 按路牌（>6）落最右叶，[7,8,9]（满，合法）。插 10 → 再溢出：分裂 [7,8] 与 [10]，界碑 9 上升 → 根 [3,6,9]。十次插入，只有三次结构事件

删除是插入的镜像。 节点跌破半满，先经由父节点向兄弟借键；兄弟没有余量，就两节点合并、父节点的分隔键撤下来；根被掏空就摘除，树矮一层——高度变化同样只经根。

账单。 查找均匀地便宜：最坏 ≈ 平均，3–4 次读页，任何输入顺序都伤不了结构（顺序插入只是在最右边缘反复分裂）。代价在写：写落在结构中间——随机 IO、页分裂、碎片。这张账单正是 wal 式思维、乃至 LSM 树存在的理由：把随机结构写改造成顺序追加。随机读页为什么是这里的计价单位，见 io-block-size-and-iops。

附记——字母 B。 B 代表什么，发明人 Bayer 与 McCreight（1970）从未正式定义。候选：Balanced（平衡）、Bayer（姓氏）、Boeing（波音，两人就职的实验室）、Broad（宽）。诚实的答法——"官方未定义，一般取 Balanced 或 Bayer"——就是面试安全版。