AVL--B+树

二叉平衡树（AVL）：即AVL树是一颗二叉搜索树是，它的左右子子树的高度之差（平衡因子）的绝对值不大于1，并且它的左右子树也是一颗AVL树。

n个节点的AVL树，高度在log(n),插入、删除、查找的时间复杂度保持log(n)。左旋和右旋保持平衡。

红黑树：红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：左旋、右旋和变色保持平衡。
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

性质6：通过着色限制红黑树确保没有一条路径比其他路径长出两倍。
n个节点的红黑树，插入、删除、查找的时间复杂度保持log(n)。左旋和右旋保持平衡。

红黑树较AVL树优点: AVL树是高度平衡的，频繁地插入和删除会引起频繁地rebalance,导致效率下降。红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转，红黑树性能较稳定。

B+树的特征：

• 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；
• 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
• 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；