常用树(红黑树，B树等)的性质

红黑树：一种特殊的二叉搜索树，满足如下性质： 
(1)根节点是黑的 
(2)每个叶节点是黑的 
(3)如果一个节点是红的，它的两个孩子节点是黑的 
(4)每个节点要么是红的，要么是黑的 
(5)对于任意节点而言，其到叶节点的每条路径到包含相同数目的黑节点
B树：是为磁盘或者其他存储设备设计的一种多叉平衡查找树。
一颗m阶的B树特性如下：
(1)树中每个节点最多含有m个孩子(m ≥ 2)；
(2)除根结点和叶节点外，其他每个节点至少有ceil(m/2)个孩子；
(3)根节点至少有两个孩子(除非B树只有一个节点-根节点)；
(4)所有叶节点出现在同一层，叶节点不包含任何关键字信息；
(5)每个非终端节点含有n个关键字，即(n,P0,K1,P1,K2,P2,...,Kn,Pn)。其中Ki(i = 1,2,...,n)为关键字,且关键字按顺序升序排列Ki-1且指针Pi-1指向子树中的所有节点的关键字均小于Ki且都大于Ki-1，关键字的个数n必须满足ceil(m/2)-1≤n≤m-1。比如,有j个孩子的非叶节点恰好有j-1个关键字。
B+树是应文件系统所需所产生的一种B树的变形树。m阶B+树与m阶B树的不同点在于：
(1)有n颗子树的节点含有n个关键字
(2)所有的叶节点中都包含全部关键字的信息以及指向含有这些关键字记录的指针，且叶节点本身按关键字的大小自小而大的顺序连接(而B树的叶节点并没有包含全部需要查找的信息);
(3)所有的非终端节点可以看成是索引部分，节点中仅含有其子树根节点中最大（或最小）关键字(而B树的非终端节点也包含需要查找的有效信息)
B*树是B+树的变种，在B+树的基础上，B*树种非根节点和非叶节点再增加了指向兄弟节点的指针；B*树定义了非叶节点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。