了解红黑树之前先认识一下B树。
一、B树
1.1. 基本概念
B树（也写作B-tree、B-树）是一种平衡的多路搜索树，多用于文件系统、数据库的实现。
仔细观察B树，有什么眼前一亮的特点？
- 1个节点可以存储超过2个元素、可以拥有超过2个子节点
- 拥有二叉搜索树的一些性质
- 平衡，每个节点的所有子树高度一致
- 比较矮
1.2. m阶B树的性质（m≥2）
阶的意思是一个节点的最大子节点个数，例如3阶B树意思是最多有3个子节点（如上图节点23 30拥有3个子节点：节点20 21，节点24，节点31）。
假设一个节点存储的元素个数为x：
- 根节点元素个数：
1 ≤ x ≤ m − 1 - 非根节点元素个数：
ceilf(m/2) − 1 ≤ x ≤ m − 1
如果有子节点，子节点个数：y = x + 1
- 根节点的子节点个数：
2 ≤ y ≤ m - 非根节点的子节点个数：
ceilf(m/2) ≤ y ≤ m
例：
- 比如
m = 3，2 ≤ y ≤ 3，因此可以称为(2, 3)树、2-3树 - 比如
m = 4，2 ≤ y ≤ 4，因此可以称为(2, 4)树、2-3-4-树 - 比如
m = 5，3 ≤ y ≤ 5，因此可以称为(3, 5)树 - 比如
m = 6，3 ≤ y ≤ 6，因此可以称为(3, 6)树 - 比如
m = 7，4 ≤ y ≤ 7，因此可以称为(4, 7)树
思考1：如果
m = 2，那B树是什么样子？是一颗二叉树。思考2：猜猜数据库实现中一般用几阶B树？200 ~ 300。
1.3. B树 VS 二叉搜索树
B树和二叉搜索树，在逻辑上是等价的。二叉搜索树的多代节点合并后，可以获得一个超级节点（能存储多个元素），然后就可以成为B树。
- 2代合并的超级节点，最多拥有4个子节点(至少是 4阶B树)
- 3代合并的超级节点，最多拥有8个子节点(至少是 8阶B树)
- n代合并的超级节点，最多拥有
2^n个子节点（至少是2^n阶B树）
m阶B树，最多需要n = logm代合并。
1.4. 搜索
B树搜索跟二叉搜索树的搜索类似，都是元素值比较后从左右子树中进行查找。
- 先在节点内部从小到大开始搜索元素；
- 如果命中，搜索结束；
- 如果未命中，再去对应的子节点中搜索元素，重复步骤1。
1.5. 添加
新添加的元素必定是添加到叶子节点。
B树示例：
插入55：
再插入95
再插入98呢？（假设这是一棵4阶B树）。最右下角的叶子节点的元素个数将超过限制，这种现象可以称之为:上溢（overflow）。
1.5.1. 上溢的解决（假设5阶）
上溢节点的元素个数必然等于m。
假设上溢节点最中间元素的位置为
k（如果中间元素是两个，选任意一个都可以，具体需要看代码实现），将k位置的元素向上与父节点合并；将
[0, k-1]和[k + 1, m - 1]位置的元素分裂成2个子节点，这2个子节点的元素个数，必然都不会低于最低限制ceilf(m/2) − 1；
- 一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决，最极端的情况，有可能一直分裂到根节点。
上溢的解决方案有了，回到之前的问题：
插入98（原节点插入98后上溢，让95向上和父节点合并（60 80 95），并把上溢节点分割为90和98、100两个子节点）：
插入52（原节点插入52后不会上溢，直接插入）：
插入54（原节点插入54后上溢，让52向上和父节点合并（52 60 80 95），并把上溢节点分割为50和54、55两个子节点，由于合并后还是上溢，让60向上和父节点合并（40 60），并把上溢节点分割为52和80 95两个子节点）：
1.6. 删除
1.6.1. 删除 - 叶子节点
假如需要删除的元素在叶子节点中，那么直接删除即可。
例如，删除30：
1.6.2. 删除 - 非叶子节点
假如需要删除的元素在非叶子节点中：
- 先找到前驱或后继元素，覆盖所需删除元素的值；
- 再把前驱或后继元素删除。
例如，删除60：
非叶子节点的前驱或后继元素，必定在叶子节点中。所以这里的删除前驱或后继元素，就是最开始提到的情况：删除的元素在叶子节点中。真正的删除元素都是发生在叶子节点中。
为什么不能直接删除？因为会改变原节点的子节点个数，比如原节点元素个数是两个（
40 60），可以对应3个子节点，删除60后节点元素个数就剩下一个，只能对应2个子节点，需要不断变换节点才能满足要求。相比使用前驱或后继就复杂很多，甚至无法成为一颗B树。
假设下面是一棵5阶B树，删除22：
发现叶子节点被删掉一个元素后，元素个数可能会低于最低限制（≥ ceilf(m/2) − 1, 即 ≥ 2），这种现象称为:下溢（underflow）。
1.6.3. 下溢的解决（假设5阶）
下溢节点的元素数量必然等于ceilf(m/2) − 2。
- 如果下溢节点临近的兄弟节点，有至少
ceilf(m/2)个元素，可以向其借一个元素。
- 将父节点的元素
b插入到下溢节点的0位置(最小位置) - 用兄弟节点的元素
a(最大的元素)替代父节点的元素b - 这种操作其实就是：旋转
- 如果下溢节点临近的兄弟节点，只有
ceilf(m/2) - 1个元素。
- 将父节点的元素
b挪下来跟左右子节点进行合并 - 合并后的节点元素个数等于
ceilf(m/2) + ceilf(m/2) − 2，不超过m − 1 - 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播，最极端的情况是向上传播到根节点。
上溢到根节点会导致B树高度加1（根节点上溢只能继续往上增加节点），下溢到根节点会导致B树高度减1（根节点下溢只能和子节点合并）。
1.7. 4阶B树
如果先学习4阶B树(2-3-4树)，将能更好地学习理解红黑树。
4阶B树的性质：
- 所有节点能存储的元素个数（根节点和非根节点）：
1 ≤ x ≤ 3 - 所有非叶子节点的子节点个数：
2 ≤ y ≤ 4
从1添加到22：
可以自己练习从1删除到22，以此加深对B树的理解。动画演示：https://www.cs.usfca.edu/~galles/visualization/BTree