AVL树，红黑树，B树，B+树

AVL树

概念：AVL树称为平衡二叉树，对于平衡二叉树，他的每个节点的左子树和右子树之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间旋转，将二叉树维持在一个平衡态。

红黑树

红黑树的特点：
1.每一个节点不是红色就是黑色
2.跟总是黑色的
3.如果节点是红色的，那么它的子节点必须是黑色的（反之并不一定必须为真）
4.从根节点到叶子节点的每条路径，必须包含相同数目的黑色节点
红黑树比AVL树的优势在哪里
首先红黑树是不符合AVL树的平衡条件的；但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候选择次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。红黑树的插入效率更高。

B树

特征：
1.任意非叶子节点节点最多只有M个儿子
2.跟节点的儿子树为[2,M]
3.除根节点以外的叶子节点的儿子树为[M/2,M],向上取整
4.非叶子节点的关键个数=儿子树-1
5.所有叶子节点位于同一层
6.k个关键字把节点拆成k+1段，分别指向k+1个儿子，同时满足查找树的大小关系。
特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；

B+树

1.含有K个关键字元素的非叶子节点有k颗子树，这些关键字不保存数据，只用来索引，所有数据都保持在叶子节点中（而b树是每个关键字都保持数据）
2.所有的叶子节点包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序连接。
3.所有的非叶子节点可以看成索引部分，节点中仅含其子树的最大关键字。
4.通常在B+树上有两个头指针，一个指向跟节点，一个指向关键字小的叶子节点。
5.同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。