[转]B树、B树、B+树、B*树知识详解

本文将详细介绍数据结构中的一些常用的搜索树结构&＃xff0c;包括&＃xff1a;B树、B-树、B&＃43;树、B*树&＃xff1b;分别介绍这些树结构的定义、特征、搜索方法、性能等情况&＃xff0c;最后给出了一个简要的总结。

一、 B树

B树即二叉搜索树&＃xff0c;它的特征是&＃xff1a;

1.所有非叶子结点至多拥有两个儿子&＃xff08;Left和Right&＃xff09;&＃xff1b;

2.所有结点存储一个关键字&＃xff1b;

3.非叶子结点的左指针指向小于其关键字的子树&＃xff0c;右指针指向大于其关键字的子树&＃xff1b;

一颗典型的B树图如下所示&＃xff1a;

B树的搜索&＃xff1a;

从根结点开始&＃xff0c;如果查询的关键字与结点的关键字相等&＃xff0c;那么就命中&＃xff1b;否则&＃xff0c;如果查询关键字比结点关键字小&＃xff0c;就进入左儿子&＃xff1b;如果比结点关键字大&＃xff0c;就进入右儿子&＃xff1b;如果左儿子或右儿子的指针为空&＃xff0c;则报告找不到相应的关键字&＃xff1b;

B树的性能&＃xff1a;

如果B树的所有非叶子结点的左右子树的结点数目均保持差不多&＃xff08;平衡&＃xff09;&＃xff0c;那么B树的搜索性能逼近二分查找&＃xff1b;但它比连续内存空间的二分查找的优点是&＃xff0c;改变B树结构&＃xff08;插入与删除结点&＃xff09;不需要移动大段的内存数据&＃xff0c;甚至通常是常数开销&＃xff0c;如下图所示&＃xff1a;

但B树在经过多次插入与删除后&＃xff0c;有可能导致不同的结构&＃xff0c;如下图&＃xff1a;

右边也是一个B树&＃xff0c;但它的搜索性能已经是线性的了&＃xff1b;同样的关键字集合有可能导致不同的树结构索引&＃xff1b;所以&＃xff0c;使用B树还要考虑尽可能让B树保持左图的结构&＃xff0c;和避免右图的结构&＃xff0c;也就是所谓的“平衡”问题&＃xff1b;

实际使用的B树都是在原B树的基础上加上平衡算法&＃xff0c;即“平衡二叉树”&＃xff1b;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键&＃xff1b;平衡算法是一种在B树中插入和删除结点的策略&＃xff1b;

二、 B-树

B-树是一种多路搜索树&＃xff08;并不是二叉的&＃xff09;&＃xff0c;必须满足以下条件&＃xff1a;

1.定义任意非叶子结点最多只有M个儿子&＃xff1b;且M>2&＃xff1b;

2.根结点的儿子数为[2, M]&＃xff1b;

3.除根结点以外的非叶子结点的儿子数为[M/2, M]&＃xff1b;

4.每个结点存放至少M/2-1&＃xff08;取上整&＃xff09;和至多M-1个关键字&＃xff1b;&＃xff08;至少2个关键字&＃xff09;

5.非叶子结点的关键字个数&＃61;指向儿子的指针个数-1&＃xff1b;

6.非叶子结点的关键字&＃xff1a;K[1], K[2], …, K[M-1]&＃xff1b;且K[i]

7.非叶子结点的指针&＃xff1a;P[1], P[2], …, P[M]&＃xff1b;其中P[1]指向关键字小于K[1]的子树&＃xff0c;P[M]指向关键字大于K[M-1]的子树&＃xff0c;其它P[i]指向关键字属于(K[i-1], K[i])的子树&＃xff1b;

8.所有叶子结点位于同一层&＃xff1b;

一颗典型的B-树如下图所示&＃xff08;设M&＃61;3&＃xff09;&＃xff1a;

B-树的搜索&＃xff1a;

从根结点开始&＃xff0c;对结点内的关键字&＃xff08;有序&＃xff09;序列进行二分查找&＃xff0c;如果命中则结束&＃xff0c;否则进入查询关键字所属范围的儿子结点&＃xff1b;重复&＃xff0c;直到所对应的儿子指针为空&＃xff0c;或已经是叶子结点&＃xff1b;

B-树的特性&＃xff1a;

1.关键字集合分布在整颗树中&＃xff1b;

2.任何一个关键字出现且只出现在一个结点中&＃xff1b;

3.搜索有可能在非叶子结点结束&＃xff1b;

4.其搜索性能等价于在关键字全集内做一次二分查找&＃xff1b;

5.自动层次控制&＃xff1b;

B-树的性能&＃xff1a;

由于限制了除根结点以外的非叶子结点&＃xff0c;至少含有M/2个儿子&＃xff0c;确保了结点的至少利用率&＃xff0c;其最底搜索性能为&＃xff1a;

其中&＃xff0c;M为设定的非叶子结点最多子树个数&＃xff0c;N为关键字总数&＃xff1b;所以B-树的性能总是等价于二分查找&＃xff08;与M值无关&＃xff09;&＃xff0c;也就没有B树平衡的问题&＃xff1b;

由于M/2的限制&＃xff0c;在插入结点时&＃xff0c;如果结点已满&＃xff0c;需要将结点分裂为两个各占M/2的结点&＃xff1b;删除结点时&＃xff0c;需将两个不足M/2的兄弟结点合并&＃xff1b;

三、 B&＃43;树

B&＃43;树是B-树的变体&＃xff0c;也是一种多路搜索树&＃xff0c;它必须满足&＃xff1a;

1.其定义基本与B-树同&＃xff0c;除了&＃xff1a;

2.非叶子结点的子树指针与关键字个数相同&＃xff1b;

3.非叶子结点的子树指针P[i]&＃xff0c;指向关键字值属于[K[i], K[i&＃43;1])的子树

&＃xff08;B-树是开区间&＃xff09;&＃xff1b;

4.为所有叶子结点增加一个链指针&＃xff1b;

5.所有关键字都在叶子结点出现&＃xff1b;

一颗典型的B&＃43;树如下图所示&＃xff08;设M&＃61;3&＃xff09;&＃xff1a;

B&＃43;树的搜索&＃xff1a;

B&＃43;的搜索与B-树也基本相同&＃xff0c;区别是B&＃43;树只有达到叶子结点才命中&＃xff08;B-树可以在非叶子结点命中&＃xff09;&＃xff0c;其性能也等价于在关键字全集做一次二分查找&＃xff1b;

B&＃43;树的特征&＃xff1a;

1.所有关键字都出现在叶子结点的链表中&＃xff08;稠密索引&＃xff09;&＃xff0c;且链表中的关键字恰好

是有序的&＃xff1b;

2.不可能在非叶子结点命中&＃xff1b;

3.非叶子结点相当于是叶子结点的索引&＃xff08;稀疏索引&＃xff09;&＃xff0c;叶子结点相当于是存储&＃xff08;关键字&＃xff09;数据的数据层&＃xff1b;

4.更适合文件索引系统&＃xff1b;

四、 B*树

B*树是B&＃43;树的变体&＃xff0c;在B&＃43;树的非根和非叶子结点再增加指向兄弟的指针&＃xff0c;一颗典型的B*树如下图所示&＃xff1a;

B*树的特点&＃xff1a;

B*树定义了非叶子结点关键字个数至少为(2/3)*M&＃xff0c;即块的最低使用率为2/3代替B&＃43;树的1/2&＃xff09;&＃xff1b;

B&＃43;树的分裂&＃xff1a;

当一个结点满时&＃xff0c;分配一个新的结点&＃xff0c;并将原结点中1/2的数据复制到新结点&＃xff0c;最后在父结点中增加新结点的指针&＃xff1b;B&＃43;树的分裂只影响原结点和父结点&＃xff0c;而不会影响兄弟结点&＃xff0c;所以它不需要指向兄弟的指针&＃xff1b;

B*树的分裂&＃xff1a;

当一个结点满时&＃xff0c;如果它的下一个兄弟结点未满&＃xff0c;那么将一部分数据移到兄弟结点中&＃xff0c;再在原结点插入关键字&＃xff0c;最后修改父结点中兄弟结点的关键字&＃xff08;因为兄弟结点的关键字范围改变了&＃xff09;&＃xff1b;如果兄弟也满了&＃xff0c;则在原结点与兄弟结点之间增加新结点&＃xff0c;并各复制1/3的数据到新结点&＃xff0c;最后在父结点增加新结点的指针&＃xff1b;

所以&＃xff0c;B*树分配新结点的概率比B&＃43;树要低&＃xff0c;空间使用率更高&＃xff1b;

五、 总结

B树&＃xff1a;

二叉树&＃xff0c;每个结点只存储一个关键字&＃xff0c;等于则命中&＃xff0c;小于走左结点&＃xff0c;大于

走右结点&＃xff1b;

B-树&＃xff1a;

多路搜索树&＃xff0c;每个结点存储M/2到M个关键字&＃xff0c;非叶子结点存储指向关键字范围的子结点&＃xff1b;所有关键字在整颗树中出现&＃xff0c;且只出现一次&＃xff0c;非叶子结点可以命中&＃xff1b;

B&＃43;树&＃xff1a;

在B-树基础上&＃xff0c;为叶子结点增加链表指针&＃xff0c;所有关键字都在叶子结点中出现&＃xff0c;非叶子结点作为叶子结点的索引&＃xff1b;B&＃43;树总是到叶子结点才命中&＃xff1b;

B*树&＃xff1a;

在B&＃43;树基础上&＃xff0c;为非叶子结点也增加链表指针&＃xff0c;将结点的最低利用率从1/2提高到2/3&＃xff1b;

原文地址&＃xff1a;http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html