几种平衡树的总结

1、2⑶⑷树介绍
2⑶⑷树是1种多叉树(multiway tree)，它的每一个节点最多有4个子节点和3个数据项，2⑶⑷ 树可以看作是阶为4 的B树。B树是另外一种平衡的多叉树，专门用在外部存储中来组织数据(通常是指磁盘驱动器)。B树中的节点可以有几时或几百个。
2⑶⑷树名字中的2、3、4的含义是指1个节点可能含有的子节点数。
有1个数据项的节点总是有2个子节点
有2个数据项的节点总是有3个子节点
有3个数据项的节点总是有4个子节点
简言之，非叶子节点的子节点数总是比它含有的数据项多1
在2⑶⑷树中不允许1个节点只有1个链接,这与传统的2叉树不同。
2、B树、B+树
2叉树提供了良好的性能，但是当数据有序插入时会失去平衡，2⑶⑷树和2⑶树是1种平衡树,是多路的，而红-黑树（见上1篇文章）是1种2叉平衡树，通过严格的红黑规则保持平衡。B树是1种平衡的多路查找树，可以看作1种扩大的2⑶⑷树，它的数据项个数和子节点数没有限制(如果结点的元素数量非常多的话那就退化成节点内部的线性查找了)，在文件系统中有所利用，主要用作文件的索引。
B树插入节点要注意从子节点开始分裂,1直上溯到根
B+树是B树的1种变型
B+树中的非叶子节点不是终究指向文件内容的节点，而只是叶子节点中关键字的索引。所有的叶子节点包括了全部关键字的信息，且叶子节点本身依关键字自小而大顺序链接。所以任何关键字的查找都必须走1条从根节点到叶子节点的路(致使每个数据的查询效力相当)。

总而言之，B 树在提高了磁盘IO 性能的同时并没有解决元素遍历效力低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就能够实现整棵树的遍历，支持基于范围的查询，而B树不支持range-query 这样的操作（或说效力太低）。

通过以上介绍，大致将B 树，B+树，B*树总结以下：
● B 树：有序数组+平衡多叉树；
● B+树：有序数组链表+平衡多叉树；
● B*树：1棵饱满的B+树。
B树相干的参考资料http://blog.csdn.net/v_july_v/article/details/6530142