B树、B+树、红黑树

本科学《数据结构》时，就已经学过AVL树这一高效的查找数据结构，然而对于B树、B+树以及红黑树，却只是蜻蜓点水。本篇博客将从逻辑角度研究这三类平衡树的增删改查操作，并比较其效率和应用场景。

B树

B树（B-tree）（因为英文的这种写法，也尝尝被误认为是B-树），是一种自平衡的树。一个 $m$ 阶的B树有如下性质：

1. 最多有 $m$ 个子树，即最多有 $m-1$ 个键；
2. 除了根节点外，其他节点最少有 $\lceil \frac{m}{2}\rceil$ 个子树；
3. 拥有 $k$ 个子树的非叶子结点拥有 $k-1$ 个元素，且升序排列；
4. 所有的叶子结点在同一层。

查找与遍历

根据B树键的有序性，不难直接思考得出查找与遍历的算法，略。

插入

插入新元素时，主要需要注意B树的第一条性质。首先可以说服自己，插入一定是发生在叶子节点。为了简便起见，我们先考虑几种比较dummy的情况：

1. 如果树为空，直接创建一个新的节点；
2. 如果树不为空，找到一个适合插入的叶子结点位置，此时如果叶子结点还有空位置，则直接按照升序的原则将元素插入。
   接下来是重头戏：如果叶子结点已经有 $m-1$ 个键，那么就要分裂当前这个叶节点。
   
   不妨假设叶节点可以容下 $m$ 个键，于是我们可以将新元素存入叶节点中。然后我们取这个叶节点的中位数，将这个中位数提到父节点中，中位数左边的节点作为一个新节点，右边的节点作为一个新节点，则叶子结点分裂完成。如果此时父节点的键数也满，则对父节点进行递归操作。

删除

删除可能发生在叶子结点上，也可以发生在非叶子结点上，并且删除时，主要注意满足B树的性质2。
为简便起见，我们先不考虑性质2，当要删除的元素在叶子结点上时，直接删除即可；当要删除的元素在非叶子结点上时，删除该元素后，还需要从子节点中提取一个元素以填补空白，可以是被删除节点的前继（左子树的最大键）或后继（右子树的最小键）。

在上图的B树中删除键为21的节点：

接着删除键为27的节点：

如果不考虑B树的性质2，那么到这里就结束了。但是我们为了维持B树的性质2，还需要进行额外的操作。
当前节点的键数目低于下限后，就要考虑从兄弟节点借元素（左右兄弟都可以，这里统一取左兄弟）。根据兄弟节点的键够不够，还可以分为两种情况：

• 兄弟节点的键大于 $\lceil \frac{m}{2}\rceil-1$，即借出去一个自己也不会太少：将父节点的元素下移，并将兄弟节点的最大键上移（这种情况很像AVL树的右旋）；
• 兄弟节点的键等于 $\lceil \frac{m}{2}\rceil$：就要考虑将两个兄弟节点合并，将父结点中两个兄弟之间的那个元素取下来，并合并左右兄弟。!
  对上图的B树进行调整后：
  
  删除节点32会引起第二种情况的调整：
  
  
  当然了，这里父节点的键又低于下限了，所以需要递归调整。

B+树

B+树可以看成是B树的一个变种，两种树的大部分性质是类似了，只有一点不同，即B+树的非叶子结点不储存数据，只存键，所有数据都保存在叶子结点中。也由于B+树的这个特性，为了方便范围查询，叶子结点之间还会用指针串联起来：

查找、遍历

除了叶子节点存在后继指针外，与B树类似，略。

插入

插入需要分插入叶子类型（值）和插入非叶子（索引）两种情况，与B树也很类似。
不同的是，在插入叶子类型时，只是将键上移到父节点中，小于等于中位数的作为左兄弟，大于中位数的作为右兄弟（回忆B树的分裂，小于中位数的作为左兄弟，等于中位数的作为父结点的新元素，大于中位数的作为右兄弟）。最后中位数的键（只有键，没有值）上移，对父节点进行递归操作。

红黑树

红黑树有以下几个性质：

1. 节点分为红色和黑色两种；
2. 根是黑色；
3. 叶子结点即 null 结点，必须为黑色；
4. 红色结点的子节点和父结点都是黑色；
5. 从根结点到叶子结点的所有路径都包含相同数目的黑色结点；
   
   为了方便起见，接下来所有的 null 节点都被省略。

红黑树的等价

理解红黑树特点的最重要的一点，就是将其与B树等价，对于下面这样结构的红黑树：

可以将其与一棵4阶B树等价：

不一样的是，普通的4阶B树是新元素是从从下标0开始插入的，而红黑树等价的4阶B树是先插入下标1，接下来有新元素时，再根据键的大小来决定是插入下标0还是下标2。

插入

在红黑树中进行插入需要分很多种情况进行讨论。最特殊的一种就是，原来的红黑树是空树，此时新插入的节点需要设定为黑色，以满足性质2。
接下来是其他情况，其他情况下，新插入的节点必须被染成红色，以保证以最小的可能性破坏性质5。根据被插入节点的节点数目，可以分为12种情况（在上面这个B树中的叶子结点中恰好包含了所有情况），可以说是相当复杂。但是也不是没有规律可以寻找，我们依旧可以将红黑树与B树等价起来，然后探究各种情况的本质，分类讨论。

直接符合红黑树性质的4种情况

上述这4种情况（父结点为黑色）在插入时不会破坏红黑树的性质，可以直接插入。
这4种情况映射到B树的本质，就是直接在叶子结点的开头或结尾插入了一个元素，并且恰好插入到了下标0或2的位置。

旋转并染色就可以解决的4种情况

父节点为红色，且没有叔节点的情况是可以通过旋转+染色就可以解决的。根据父结点在爷结点的位置以及新插入节点在父结点的位置，共可以分为以下4种情况：

LL与RR

这2种情况映射到B树的本质，就是在叶子结点的开头或结尾插入了一个元素，但是插入到了下标-1或3的位置，需要整体平移（左旋或右旋+染色）。

RL与LR

这2种情况映射到B树的本质，就是在叶子结点的中间插入了一个元素，需要重新排序（左旋并右旋或右旋并左旋+染色）。

需要上移的4种情况

父结点为红色，且有叔节点，这种情况对应着B树种需要上移的情况（上图中的10、20、30、36）。具体地，根据父结点在爷结点的位置，又可以分四种情况，这里举两种典型例子来说明：

LL与LR的情况

LL的情况：

LL的情况调整后：

RL与LR的情况

RL的情况

RL调整后

总结一下这4种情况，本质上都是在B树中的一个满的叶子节点插入，然后将中位数上移。但是使用红黑树的一个很大好处就是，如上图所示，虽然在等价的B树中，需要上移和分裂等操作，但是我们实际上只要在红黑树中调整颜色即可，省去了很多操作。

删除

删除依旧分了很多种情况，回顾一下B树中元素的删除，我们分了元素是否在叶子结点上来讨论，对于红黑树，也可以采用类似的思路。当删除的元素在等价B树的非叶子结点上时，则直接删除，并使用前继或后继来填充，并递归操作。所以接下来只需要考虑元素在等价B树的叶子节点上的情况即可。

没有突破键数目下限的情况

首先是dummy的情况，如果是红色，可以直接删除。
其次，是如图是25、46、76这3种删除节点为黑色的情况，它们有一个子节点，所以也可以直接删除，并使用儿子节点来代替（并需要将后继结点染色）。
下面是删除46、76后的红黑树。

对于删除25的情况，也只需要任选一个儿子节点来替代即可。
对应到B树中，这几种情况都没有突破4阶B树的至少一个键的性质。

突破键数目下限的情况

回顾B树中，如果结点的键数目突破下限，则需要从兄弟节点借一个元素。在上面这棵红黑树中，如果我们要删除88这个节点，则相当于把B树的叶节点数目删到0了，此时就要从兄弟节点借一个元素（其实是从父结点借元素，然后兄弟节点上移）。
接下来又可以分两种情况：

兄弟节点儿子数目够

父节点下移，兄弟节点上移。对应到红黑树的操作就是旋转，此时需要根据自己和兄弟的位置情况判断是LL、RR、RL、LR四种情况中的哪一种（兄弟节点有两个子节点时，LL和RR都可以）。

兄弟节点儿子数目不够

对应B树中的操作就是从父结点下移一个元素，并合并两个兄弟节点。 这里情况比较特殊，我们可以把被删除元素所在节点看成一个“键数为0”，但没有被删除的B树结点。此处根据B树父结点的值位置，还可以分出两种情况：
情况1：键位于1和2：

情况2：键位于0和1：

两种情况调整后的结构均为：

但是，由于55和80这两个节点的关系不一样，所以具体的代码也是不一样的，但是对应B树的逻辑上的操作是一样的。
情况3：特殊情况，需要注意，由于这种情况导致了父结点的下移，所以需要使用递归，把父结点80也当做被删除节点：

删除（规约版本）

经过上一节讨论可以发现，红黑只有当被删除节点无子节点时，才需要调整。而这个调整的过程又十分繁琐，需要考虑的情况非常多，而根据红黑树从入门到看开这篇优质文章以及《算法导论》的规约，可以得到以下四个情形：

对比

回顾一下整篇文章，对AVL树、B树、B+树以及红黑树做一个总结。

B树、B+树

首先B树与B+树的对比，B+树将所有数据都存储在叶子结点，这个特点使内存中的索引与磁盘中的数据分离，适合作为数据库的索引。并且叶子结点之间的链表链接极大地方便了范围查询。
而B树通过多路平衡设计，减少了平衡树的高度，加快搜索效率，适合文件系统，以及需要直接访问内部节点的场景。
它们的查询、插入和删除效率均为 $O(\log n)$

AVL树和红黑树

AVL树和红黑树最大的特点就是AVL树是严格平衡的，这导致插入和删除操作较慢，而红黑树对高度要求不是特别严格，可以以更少的旋转次数完成调整。也正是因为这个，在查找速度上来说，AVL树的查找速度更快。
总的来说，对于数据需要频繁插入和删除的场景，使用红黑树，而数据修改较少的场景，使用AVL树。

4阶B树与红黑树

既4阶B树与红黑树是同构的，那么为什么各大语言的内置库都是使用红黑树而不是B树呢？询问Deepseek，我认为内存效率是最主要的因素：

红黑树的节点体积更小（仅需存储颜色位+两个指针），在内存中分布更紧凑，​​缓存局部性（Cache Locality）​​更好。而2-3-4树的节点需要存储多个键和子节点指针，单个节点体积更大，遍历时可能触发更多缓存未命中，影响性能。​

参考链接：

【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树
OI Wiki
一文搞懂B树、B-树、B+树
红黑树从入门到看开