2015年软件水平考试程序员考点整理（9）
发布时间：2012/5/26 23:50:51 来源：城市网学院 编辑：ziteng
13、B树、B-树、B+树、B*树、红黑树和trie树
(1)B树:即二叉搜索树.
1.所有非叶子结点至多拥有两个儿子(Left和Right);
2.所有结点各存储一个关头字;
3.非叶子结点的左指针指向小于其关头字的子树，右指针指向大于其关头字的子树;
如：
B树的搜索，纲要结点起头，如不美观发芽的关头字与结点的关头字相等，那么就射中;否则，如不美观发芽关头字比结点关头字小，就进入左儿子;如不美观比结点关头字大，就进入右儿子;如不美观左儿子或右儿子的指针为空，则陈述找不到响应的关头字;
如不美观B树的所有非叶子结点的摆布子树的结点数目均连结差不多(平衡)，那么B树的搜索机能迫近二分查找;但它比持续内存空间的二分查找的利益是，改变B树结构(插入与删除结点)不需要移动大段的内存数据，甚至凡是是常数开销;
如：
但B树在经由多次插入与删除后，有可能导致分歧的结构：
右边也是一个B树，但它的搜索机能已经是线性的了;同样的关头字集结有可能导致分歧的树结构索引;所以，使用B树还要考虑尽可能让B树连结左图的结构，和避免右图的结构，也就是所谓的“平衡”问题;
现实使用的B树都是在原B树的基本上加上平衡算法，即“平衡二叉树”;若何连结B树结点分布平均的平衡算法是平衡二叉树的关头;平衡算法是一种在B树中插入和删除结点的策略;
(2)B-树
是一种多路搜索树(并不是二叉的), 多路平衡查找树：
1.界说肆意非叶子结点最多只有M个儿子;且M>2;
2.根结点的儿子数为[2, M];
3.除根结点以外的非叶子结点的儿子数为[M/2, M];
4.每个结点存放至少M/2-1(取上整)和至多M-1个关头字;(至少2个关头字)
5.非叶子结点的关头字个数=指向儿子的指针个数-1;
6.非叶子结点的关头字：K[1], K[2], …, K[M-1];且K[i] < K[i+1];
7.非叶子结点的指针：P[1], P[2], …, P[M];其中P[1]指向关头字小于K[1]的子树，P[M]指向关头字大于K[M-1]的子树，其它P[i]指向关头字属于(K[i-1], K[i])的子树;
8.所有叶子结点位于统一层;
如：(M=3)
B-树的搜索，纲要结点起头，对结点内的关头字(有序)序列进行二分查找，如不美观射中则竣事，否则进入发芽关头字所属规模的儿子结点;一再，直到所对应的儿子指针为空，或已经是叶子结点;
B-树的特征：
1.关头字集结分布在整颗树中;
2.任何一个关头字呈现且只呈此刻一个结点中;
3.搜索有可能在非叶子结点竣事;
4.其搜索机能等价于在关头字全集内做一次二分查找;
5.自动条理节制;
因为限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了却点的至少操作率，其最底搜索机能为：
此鱿脯M为设定的非叶子结点最多子树个数，N为关头字总数;
所以B-树的机能老是等价于二分查找(与M值无关)，也就没有B树平衡的问题;
因为M/2的限制，在插入结点时，如不美观结点已满，需要将结点割裂为两个各占M/2的结点;删除结点时，需将两个不足M/2的兄弟结点合并;
(3)B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其界说根基与B-树同，除了：
2.非叶子结点的子树指针与关头字个数不异;
3.非叶子结点的子树指针P[i]，指向关头字值属于[K[i], K[i+1])的子树(B-树是开区间);
5.为所有叶子结点增添一个链指针;
6.所有关头字都在叶子结点呈现;
如：(M=3)
B+的搜索与B-树也根基不异，区别是B+树只有达到叶子结点才射中(B-树可以在非叶子结点射中)，其机能也等价于在关头字全集做一次二分查找;
B+的特征：
1.所有关头字都呈此刻叶子结点的链表中(浓密索引)，且链表中的关头字刚好是有序的;
2.不成能在非叶子结点射中;
3.非叶子结点相当于是叶子结点的索引(稀少索引)，叶子结点相当于是存储(关头字)数据的数据层;
4.更适合文件索引系统;
(4)B*树
是B+树的变体，在B+树的非根和非叶子结点再增添指向兄弟的指针;
B*树界说了非叶子结点关头字个数至少为(2/3)*M，即块的最低使用率为2/3(庖代B+树的1/2);
B+树的割裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增添新结点的指针;B+树的割裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针;
B*树的割裂：当一个结点满时，如不美观它的下矣闽兄弟结点未满，那么将一部门数据移到兄弟结点中，再在原结点插入关头字，最后改削父结点中兄弟结点的关头字(因为兄弟结点的关头字规模改变了);如不美观兄弟也满了，则在原结点与兄弟结点之间增添新结点，并各复制1/3的数据到新结点，最后在父结点增添新结点的指针;
所以，B*树分配新结点的概率比B+树要低，空间使用率更高。
