1.所有非叶子结点至多拥有两个儿子（left和right）；
2.所有结点存储一个关键字；
3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树。
搜索：从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字。
1. m阶b-树是一种多路平衡搜索树（并不是二叉的）：
2. 根结点的儿子数为[2, m]；
3. 除根结点以外的非叶子结点的儿子数为[m/2, m]；
4. 所有叶结点都为空且位于同一层；
5. 若一个非叶结点有n个孩子，那么它有n-1个关键字，结构见下：
n-1
p0
k1
p1
k2
p2
...
kn-1
pn-1
表一：非叶结点存放的数据
k[1], k[2], …, k[n-1]为非叶子结点的关键字且k[i] < k[i+1]；
p[i]为指向孩子节点的指针。其中p[i-1]所指结点的关键字全小于k[i],p[i]所指结点的关键字全大于k[i]。
b-树的搜索：从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。
b-树的插入：找到待插入结点并插入。若所在结点关键字个数等于孩子数，进行分裂。若分裂后导致父节点关键字个数等于孩子数，再进行父节点的分裂。
b-树的删除：若删除后导致所在结点关键字个数等于m/2(向上取整)-2，需要对节点进行合并。
b-树举例：
b+树也是多路平衡查找树，与b-树的区别在于：
1.含有n个关键字的结点有n个孩子。
2.b+树中所有非叶结点仅起到索引作用，不含待查元素的存储地址。
3.叶结点包含了全部元素的关键字和存储地址。
4.非叶结点的存储结构见下：
n
kn
pn
ki为关键字，pi指向的孩子结点，其关键字的最大值为ki。
举例：
红黑树是一种二叉查找树。因结点带有颜色属性而得名。
在c++ stl中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(sgi stl中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
性质：
1.每个节点都有颜色属性，非红即黑。
2.根节点和每个叶节点（nil节点，空节点）是黑色的。
3.每个红色节点的两个孩子节点都是黑色。
4.对于任意一节点，它到其所有后代叶子节点的简单路径，均包含相同数目的黑色节点。
4.左孩子<根结点<右孩子。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
自平衡二叉查找树。
avl是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择avl，如果搜索，插入删除次数几乎差不多，应该选择rb。