b树和红黑树的联系以及树学习最后知识
一、操作等价性
1、在2-3-4树的插入过程中分裂4-节点与红黑树的插入过程中的颜色变换是相等的
2、红黑树中的旋转和把2-3-4树转换成红黑树时选择哪个节点做父节点时等价的
二、效率
1、时间
层数：
红黑树——log(N+1)（底数为2）
B树——log(N+1)到log(N+1)/2（底数为2）
2-3-4树中的查找时间与平衡二叉树如红黑树大致相等，都是O(logN)
2、存储需求
三、1、外部存储的意思是在主存外保存数据，通常是在磁盘上。（应该是指c、d、e盘等的存储）
2、外部存储器比主存大，便宜，但是慢。
3、外部存储器中的数据通常需要在主存间来回传送，一次传送一块。
4、在外部存储器里的数据可以按关键字顺序有序排。这样查找很快，但插入（或删除）很慢
5、B树是多叉树，每个节点可以有几十或上百个关键字和子节点
6、B树中子节点的个数总比关键字多1.
7、为了达到最好的性能，B树通常在一个节点中保存一块的数据。
8、如果查找条件涉及多个关键字，在文件所有的记录中顺序查找可能是最实用的方法。