B 树是如何查找和插入的？为什么插入会「分裂」？

简化版

查找：从根开始，在节点内部（关键字有序）二分定位，命中就返回；否则顺着对应区间的孩子指针下降到下一层，直到找到或到叶子。插入：先查找到该插入的叶子节点，插进去；如果这个节点关键字数超过了上限（m-1），就分裂——把中间的关键字提升到父节点，节点一分为二。分裂可能连锁向上，甚至让根分裂使树长高一层。

详细版

查找

在节点内：关键字有序，用二分找目标
  命中 → 返回
  没命中 → 落在某两个关键字之间 → 顺着对应孩子指针下降一层
重复，直到命中或走到叶子仍没有（不存在）

每下降一层是一次磁盘 IO，所以查找的 IO 次数 = 树高 O(logₘn)。

插入与分裂

查找到应插入的叶子节点，把新关键字有序插进去。
若插入后该节点关键字数 ≤ m-1，完成。
若溢出（= m 个关键字），则分裂：
- 取节点的中间关键字，提升到父节点。
- 剩下的关键字分成左右两个节点，分别挂到提升上去的关键字两侧。
父节点接收了新关键字后如果也溢出，继续向上分裂；一直到根。若根也分裂，就产生一个新根，树高 +1。

完整版教学

一、查找：节点内二分 + 逐层下降

B 树查找是 BST 查找的「多路版」。区别在于每个节点内有多个有序关键字，所以在节点内部要先做一次二分查找定位到目标区间，再顺着孩子指针下降。因为节点内的比较发生在内存里（节点已被读进内存），几乎不耗时；真正的开销是每下降一层的一次磁盘 IO。所以查找性能看树高，而 B 树很矮，IO 次数少。

二、插入为什么必然从叶子开始

和 BST 一样，B 树的新关键字总是先插到叶子层——因为查找会一路走到叶子才发现「这里该放新值」。插到叶子后，只要没超容量就完事。麻烦的是超容量时怎么办——这就引出了分裂。

三、分裂：维持「至多 m-1 个关键字」的手段

一个节点最多 m-1 个关键字。插入第 m 个就「撑破」了，必须分裂来恢复约束：

4 阶 B 树（每节点最多 3 个关键字），向 [10 20 30] 插入 25：
1) 先插入变成 [10 20 25 30]  ← 4 个，溢出！
2) 取中间关键字 20（或 25，取决于取左中/右中）提升到父节点
3) 分裂成两个节点：[10]  和  [25 30]
   父节点在 20 两侧分别指向这两个节点

分裂的精髓是「中间关键字上提、节点一分为二」。这样既让本节点回到合法大小，又通过「上提」把新的分界关键字交给了父节点。

四、分裂为什么会向上连锁、让树长高

被提升的中间关键字进入父节点，父节点因此多了一个关键字。如果父节点本来就快满，这一提可能让父节点也溢出，于是父节点继续分裂、再往上提……这种连锁可能一直传到根。

如果根节点也分裂了，中间关键字无处可提，就创建一个新的根节点来接收它——这时整棵树长高一层。这是 B 树唯一长高的方式：从根部向上生长。正因为「从叶子插入、从根部长高、所有叶子始终同层」，B 树才能永远保持完美平衡。

五、复杂度

查找：O(logₘn) 次 IO。
插入：查找 O(logₘn) + 最坏一路分裂到根 O(logₘn)，总体 O(logₘn) 次 IO；分裂本身是 O(m) 的内存操作。

分裂虽然可能连锁，但和树高同阶，不影响整体 O(logₘn)。

六、常见误区与追问

考点	正确口径
查找	节点内定位 key 或下降区间
插入	总是插入到叶子
分裂	节点满时中间 key 上升，左右分成两个节点

insert key into leaf
if keys > max:
  promote median to parent
  split left/right
  if parent overflows: split upward

B 树插入分裂，是为了维护每个节点关键字数量不超过上限。

误区：B 树插入可以直接放在内部节点。 查找失败最终落到叶子区间，新 key 应插入叶子，再处理溢出。
误区：节点满了就新建一个孩子挂上去。 必须中间 key 上升到父节点，左右 key 分裂成两个节点，才能保持有序范围。
误区：分裂只会发生在叶子。 叶子分裂会把 key 推给父节点，父节点也可能溢出并继续向上分裂。
追问：根分裂会发生什么？ 根溢出时创建新根，中间 key 上升，树高增加一层。
追问：节点内查找用什么？ key 数少可线性扫描，较多时可二分；磁盘场景主要成本仍是页 IO。
追问：复杂度是多少？ 下降和分裂都受树高控制，层数 O(log_m n)。

七、加强记忆

B 树查找 = 节点内二分定位 + 顺孩子指针逐层下降（IO 次数 = 树高）。插入总是先落到叶子，若节点关键字数达到 m 就分裂：中间关键字上提到父节点、节点一分为二。分裂可能向上连锁，若根也分裂就新建根、树高 +1——这是 B 树唯一的长高方式，从而保证所有叶子始终同层、完美平衡。整体 O(logₘn)。

简化版

详细版

查找