内部节点：不超过m-1个关键码 不超过m个分支 内部节点的分支数：
对于树根：2<= n+1
其余节点：（取上界）m/2 <= n+1
B树每个节点可以视为线性序列 那么怎样表示呢？ 我们可以用向量来表示 比如：
第一个向量存放n个关键码 第二个存放相对应的n+1个引用。
含有N个关键码的M阶B树，最大高度为 h<= 1+log(m/2)[(n+1)/2] = O(logN)
提示：内部节点尽可能瘦（节点数位m/2上界）而根节点可以只分两支。
最小高度：h >= log(n)(N+1) = Ω(logmN)
B树的插入算法：
先查找，然后返回一个最近不大于插入值的关键码位置 然后关键码+1，分支也对应加一。
如果违反了约定，即插入后关键码数目上溢，则需要处理。（分裂）
此时从此组关键码中位数分裂，并将中位数关键码向上追寻，并且插入至左上两关键码的中间。
如图：
如果父节点也上溢，那么再次操作。
当然，根节点也需要有相应的上溢处理。
如果根节点也发生上溢，则也取出中位数，使之成为新的根节点。
导致B树增高（此时为两个分支）
————————————————————————— B树的删除
首先进行查找。如果找到，如果它不是叶节点，则在他的右子树中一直向左找到其直接后继，然后互换位置，进行删除。此时可能会发生关键码数目下溢，需要进行旋转。 旋转：
如果在其左边、右边的兄弟子树有足够多的关键码，则可以进行旋转
但是如果没有兄弟满足有足够多的关键码（或者不存在），则需要双方合并（此时左右兄弟至少存在其一）将上方的父节点合并下来。
父节点也可能发生下溢，如法炮制进行处理。
一种可以记录历史版本的树
例如，红色线表示相邻版本可以保留的数据 蓝线表示更新的位置。 红黑树：
1树根必为黑色
2所有外部节点也必为黑色
3其余节点：红色节点只能有黑色孩子。（红父红子必为黑） 4从任何一个外部节点到根的黑色节点数目相等（黑深度）
提升变换：
将所有红色孩子提升至与父节点同一级的高度 结果不可能有两个红色节点相邻
经过提升：
可以发现，所有底层节点的深度相同。 这也是为什么要求黑深度相等的原因。
本质：相当于一棵B树的拉伸 （2,4）树==红黑树
每一种提升后的红黑节点组合都相当于一个4阶B树
每一个节点最多拥有四个分支。 红黑树的高度：特指黑高度。 插入：
先将带插入值插入到确定位置，然后染为红色，此时第三条性质即其父亲必为黑色可能不满足。 如何修复？