红黑树

1. 节点是 red 或者 black
2. 根节点是 black
3. red 节点的子节点是 black
4. red 节点的 parent 为 black
5. 从根节点到叶子节点的所有路径上不能有两个连读的 red 节点
6. 从任一节点到子节点的所有路径上都包含相同数目的 black 节点
7. 叶子节点（外部节点或者空节点）都是 black

B-tree

balanced tree

B 树是一种平衡的多路搜索树，不是两个叉，多个叉，比如文件系统或者数据库的实现

1. 一个节点可以存储超过两个元素，可以拥有超过两个节点
2. 拥有二叉树的一些性质
3. 平衡，每个节点所有子树的高度是一致的，而且高度比较矮

n 阶 B 树的性质

假设每个节点存储的元素个数为 x

元素个数：
1. 根节点个数： 1<= x <= n-1
2. 非根节点 ：(n / 2)(向上取证) - 1 <= x <= n -1

节点个数：
1 如果有子节点，子节点的个数为 y = x + 1;
2. 非根节点：(n / 2)(向上取证) <= y <= n
3. 根节点节点个数为：2<=y<=n


5. 经过 N 代合并的超级节点，最多有 2^N 个子节点

如 n = 3,3阶B树，子节点个数（2，3），又叫2-3树
如果 n = 4 ,4 阶 B 树，子节点个数(2，4)，2-3-4树

当我们添加或者删除元素的时候，可能会导致上溢或者下溢

上溢:

新添加的元素，必定在叶子节点中。

如果添加元素，超过最大元素个数

1. 假设上溢的节点最中间的位置为 k，那么将 k 位置的元素像上面与父节点合并，将 [0,k-1]和[k+1 , m-1]的位置元素分裂成两个子节点，这连个子节点的个数必然不低于最低限制（m/2 - 1），因为已经溢出了，符合上面的性质
2. 如果向上合并，父节点溢出了，那么重复上面
3. 上溢可能会导致树的高度长高，就是添加元素上溢到根节点

删除：

1. 找到他的前驱或者后继节点，覆盖将要删除的元素
2. 再把前驱或者后继节点删除，其实真正删除的元素是在叶子节点中,因为非叶子节点的前驱或者后继，必定在叶子节点中

下溢：

叶子节点被删除一个元素之后，可能会低于最低限制（m/2 - 1）,这时候会产生下溢

1. 下溢节点的元素个数必然等于 (m/2 -2)
2. 如果兄弟节点，有至少m/2 个节点，那么借一个，将父节点的元素b下溢到溢出节点的0位置，然后兄弟节点的最大元素替代当前节点的父节点的元素b位置。
3. 如果下溢节点的兄弟节点，只有 m/2 - 1 个元素，那么将父节点的元素b，挪下来，跟左右节点进行合并，合并之后的元素个数为，m/2+m/2-2 < m-1 , 符合性质。但是这个操作可能会导致父节点下溢，可能会一直向上传播，一直到父节点。
4. 下溢可能会导致树变矮，因为有合并操作