红黑树有5个特性：
（1）每个节点只有两种颜色：红、黑。
（2）跟节点是黑色。
（3）每个叶子节点是黑色（此处的叶子节点是指为空的节点）。
（4）如果一个节点是红色的，那么他的子节点必须是黑色的。（如果节点是黑色的，那么子节点可红，可黑）
（5）从一个节点到该节点的子孙节点上所有路径上包含数目相同的黑色节点。
衍生：（1）特性5确保没有一条路径会比其他路径长出两杯。因为红黑树是一个接近平衡的二叉树。
（2）时间复杂度是O（lgn）。
（3）通常用于存储有序的数据
B树有如下特性（m阶B树）：
（1）每个最多有m个子节点
（2） 除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子
（3）如果跟节点不是叶子节点则至少含有2个子节点
（4）所有的叶子节点都出现在同一层，并且叶子节点不包含任何关键字信息
（5）每个非终端节点中包含n个关键字信息：(n，A0，K1，A1，K2，A2，......，Kn，An)，其中
a) Ki (i=1...n)为关键字，且关键字按顺序排序Ki < K(i-1)。
b) Ai为指向子树根的接点，且指针A(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [m/2]-1 <= n <= m-1
image.png
