19、B树的删除与B+树：B树的删除（节点合并）、B+树的结构特点、B+树在数据库索引中的应用
聊到B树和B+树，我脑子里第一个蹦出来的场景就是当年调MySQL索引性能的那段日子。说实话，很多人把B树当黑盒用，一遇到删除操作就懵了——节点合并、借位、下溢，这些概念听着就头大。今天咱们就把这块硬骨头啃下来。
一、B树的删除操作：节点合并的艺术
B树的删除，说白了就是保持树平衡的前提下删掉一个键。你想想看，插入的时候我们会分裂节点，那删除的时候自然就要合并节点——不然树就长歪了。
1. 删除的基本规则
B树有个核心约束：每个节点（除了根）至少要有 ⌈m/2⌉-1 个键。m是阶数。一旦删除后键数少于这个值，就叫下溢。
我习惯把删除分成三种情况：
- 情况一：删的是叶子节点中的键——直接删，完事。但删完后如果下溢了，就得处理。
- 情况二：删的是内部节点中的键——用前驱或后继键替换，然后递归删除那个替换键。
- 情况三：下溢处理——先看兄弟节点能不能借一个，不能借就合并。
核心口诀：能借不合并，借不了再合并。合并完父节点少一个键，父节点可能继续下溢——递归向上处理。
2. 借位 vs 合并
举个例子，假设一棵5阶B树（每个节点最少2个键）。某个节点删完只剩1个键，下溢了。
- 先看左兄弟：如果左兄弟键数大于最小值，从左兄弟借一个。具体做法是把父节点中分隔两个子树的键拉下来，再把左兄弟最右边的键顶上去。
- 再看右兄弟：同理。
- 都借不了：那就合并。把当前节点、兄弟节点、以及父节点中分隔它们的键，三者合并成一个新节点。
我踩过的坑：曾经在实现B树删除时，忘了合并后父节点键数减少，可能导致父节点也下溢。结果树删着删着就崩了。记住——合并是可能向上传播的，一直传到根节点为止。
3. 删除的完整流程（伪代码）
// 伪代码：B树删除
function deleteKey(node, key):
if node is leaf:
直接删除key
if node 下溢:
handleUnderflow(node)
else:
找到key所在的子树索引i
用前驱或后继替换key
deleteKey(子树, 替换键)
function handleUnderflow(node):
if node 有左兄弟且左兄弟可借:
从左兄弟借一个键
else if node 有右兄弟且右兄弟可借:
从右兄弟借一个键
else:
与兄弟合并
if 父节点下溢:
handleUnderflow(父节点)注意：根节点下溢时，如果合并后根节点变空，那就把合并后的新节点设为根。树的高度减1。
二、B+树的结构特点
B+树是B树的变种，但差别还挺大的。我当年从B树转到B+树时，第一反应是：这玩意儿怎么把数据全放叶子了？
1. B+树 vs B树 的核心区别
| 对比项 | B树 | B+树 |
|---|---|---|
| 数据存储 | 所有节点都存数据 | 只有叶子节点存数据 |
| 内部节点 | 存键和数据指针 | 只存键，作为路由 |
| 叶子节点 | 无特殊结构 | 用链表串联，形成有序序列 |
| 范围查询 | 需要中序遍历 | 直接走叶子链表，效率极高 |
| 空间利用率 | 内部节点占用数据空间 | 内部节点更小，可存更多键 |
说白了，B+树把内部节点变成了纯粹的「导航仪」，数据全堆在叶子层。这样做的好处很明显——内部节点能塞下更多键，树更矮，IO次数更少。
2. B+树的叶子链表
这个设计我特别喜欢。叶子节点之间用指针串成一个双向链表，意味着你找到第一个符合条件的叶子后，顺着链表往后走就能拿到所有数据。范围查询再也不用回溯了。
举个例子：查 "age BETWEEN 20 AND 30"。在B+树中，先找到age=20所在的叶子节点，然后顺着链表往后读，直到age>30为止。整个过程就是一次叶子扫描，没有多余的树遍历。
三、B+树在数据库索引中的应用
说到这个，我得提一句：MySQL的InnoDB引擎用的就是B+树。你建的那个主键索引，底层就是一棵B+树。
1. 为什么数据库选B+树而不是B树？
- 磁盘IO更少：内部节点不存数据，一个节点能存更多键。树的高度通常只有3-4层，查几百万条数据也就3-4次IO。
- 范围查询高效：叶子链表让范围查询变成线性扫描，不用来回跳转。
- 数据稳定性好：所有数据都在叶子层，每次查询都要走到叶子，查询时间相对稳定。
我个人的经验：在MySQL中，如果你用自增主键，B+树的叶子节点会顺序写入，几乎不需要页分裂。但如果你用UUID做主键，数据随机插入，叶子节点频繁分裂，性能会明显下降。所以——能用自增ID就别用UUID。
2. 聚簇索引 vs 非聚簇索引
InnoDB的B+树分两种：
- 聚簇索引：叶子节点存的是整行数据。一张表只有一个聚簇索引（通常是主键）。
- 非聚簇索引（二级索引）：叶子节点存的是主键值。查的时候先找到主键，再回表查聚簇索引。
嗯，这里要注意：非聚簇索引查询需要「回表」，如果查的列刚好都在索引里（覆盖索引），就不用回表。这也是为什么我经常建议把高频查询的字段加到索引里。
四、知识体系总览
下面这张图把B树删除和B+树的核心逻辑串起来了，你可以对照着看：
最后提醒一句：B+树的删除和B树类似，也是借位+合并。但因为数据全在叶子层，内部节点的删除只涉及键的调整，不涉及数据移动。实现起来反而比B树简单一些。
好了，B树的删除和B+树的核心内容就这些。你想想看，数据库索引为什么选B+树？说白了就是IO少、范围查询快、结构稳定。下次建表的时候，不妨想想你的索引底层是怎么跑的——嗯，心里有数了。