B树、B-树、B＋树和B*树

树结构中除了比较常见的二叉树外，还有B树及B树的一些变种。这些树结构在文件系统中主要用于对目录结构的管理，如对目录及文件的访问、新建、删除等，就相当于对相应的树结构的查找、插入、删除。

B树

B树的定义

B树也就是二叉搜索树，需要满足下列条件：

①所有非叶节点至多拥有两个孩子（左孩子和右孩子）；

②所有节点存储一个关键字；

③非叶节点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树。

如图1-16所示的就是一个B树。

图1-16　B树结构图

B树的查找

B树的查找，从根节点开始，如果查询的关键字与节点的关键字相等，那么就命中；否则，如果查询关键字比节点关键字小，就进入左孩子；如果比节点关键字大，就进入右孩子；如果左孩子或右孩子的指针为空，则报告找不到相应的关键字。

B-树

B−树的定义

B−树是一种平衡的多叉树，通常说m阶的B−树，必须满足如下条件：

①每个节点至多有m个孩子节点；

②除根节点和叶节点外，其他每个节点至少有m/2个孩子节点；

③若根节点不是叶节点，则至少有两个孩子节点；

④所有的叶节点在同一层，叶节点不包含任何关键字信息；

⑤有k个子节点的非终端节点最多包含k−1个关键字信息。

如图1-17所示的就是一个B−树。

图1-17　B−树结构图

B−树的查找

B−树上的查找是一个顺指针查找节点和在节点内的关键字中查找交叉进行的过程。从根节点开始，在节点包含的关键字中查找给定的关键字，找到则查找成功；否则确定给定关键字可能在的子树，重复上面的操作，直到查找成功或者指针为空为止。

B−树的插入

B−树的插入首先是在恰当的叶节点中添加关键字，如果该节点中关键字不超过m−1个，则插入成功。否则要把这个节点分裂为两个，并把中间的一个关键字拿出来插到节点的父节点里去。父节点也可能是满的，就需要再分裂，再往上插。最坏的情况，这个过程可能一直传到根节点。如果需要分裂根节点，由于根节点是没有父节点的，这时就建立一个新的根节点。插入可能导致B−树朝着根的方向生长。

例如，要在图1-18所示的一个6阶B−树结构中插入关键字“33”，因为最右边的节点中关键字的个数已经达到5个，所以不能将“33”直接插入，而是要把这个节点分裂为两个，并把中间的一个关键字“36”拿出来插到节点的父节点里。

图1-18　一个6阶B−树结构

将关键字“36”成功插入后，该B−树的结构如图1-19所示。

关键字“36”插入后的结构

B−树的删除

B−树的删除分两种情况：

①B−树中的删除操作与插入操作类似，但要稍微复杂些。如果删除的关键字不在叶节点层，则先把此关键字与它在B−树里的后继对换位置，然后再删除该关键字。

②如果删除的关键字在叶节点层，则把它从它所在的节点里去掉，这可能导致此节点所包含的关键字的个数小于m/2−1。这种情况下，考察该节点的左或右兄弟，从兄弟节点移若干个关键字到该节点中来（这也涉及它们的父节点中的一个关键字要做相应变化），使两个节点所含关键字个数基本相同。只有在兄弟节点的关键字个数也很少，刚好等于m/2−1时，这个移动不能进行。这种情况下，要把将删除关键字的节点、它的兄弟节点及它们的父节点中的一个关键字合并为一个节点。

例如，要在图1-20所示的一个3阶B−树结构中删除关键字“46”，删除后该节点的关键字个数为“0”，低于规定的最低限“1”，而它的左兄弟和右兄弟的关键字个数都为最低限“1”，所以只能把将删除关键字的节点、它的兄弟节点及它们的父节点中的一个关键字合并为一个节点。

一个3阶B−树结构

将关键字“46”删除后，该B−树的结构如图1-21所示。

关键字“46”删除后的结构

B＋树

B＋树的定义

B＋树是B−树的一种变体，它与B−树的差异在于：

①在B−树中，每个节点含有n个关键字和n＋1棵子树。而在B＋树中，每个节点含有n个关键字和n棵子数，即每个关键字对应一棵子树。

②在B−树中，每个节点（除根节点外）中的关键字个数n的取值范围是m/2−1≤n≤m−1。而在B＋树种，每个节点（除根节点外）中的关键字个数n的取值范围是m/2≤n≤m。

③B＋树中的所有叶节点包含了全部关键字及指向对应记录的指针，且所有叶节点按关键字从小到大的顺序依次链接。

④B＋树中所有非叶节点仅起到索引的作用，即节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

例如，图1-22所示的一棵3阶B＋树，其中叶节点的每个关键字下面的指针表示指向对应记录的存储位置。通常在B＋树上有两个头指针：一个指向根节点，用于从根节点起对数进行查找、插入、删除等操作；另一个指向关键字最小的叶节点，用于从最小的关键字起进行顺序查找和处理每一个叶节点中的关键字及记录。

一棵3阶B＋树结构

由于B−树只适合随机检索，B＋树同时支持随机检索和顺序检索，在实际中应用比较多，NTFS文件系统就是使用B＋树进行动态索引的。

B＋树的查找

B＋树的查找与B−树的查找类似，但是也有不同。由于与记录有关的信息都存放在叶节点中，查找时若在上层已找到待查的关键字，并不停止，而是继续沿指针向下一直查到叶节点层的关键字。此外，B＋树的所有叶节点构成一个有序链表，可以按照关键字排序的次序遍历全部记录。

上面两种方式结合起来，使得B＋树非常适合范围检索。

B＋树的插入

B＋树的插入与B−树的插入过程类似，不同的是B＋树在叶节点上进行。如果叶节点中的关键字个数超过m，就必须分裂成关键字数目大致相同的两个节点，并保证上层节点中有这两个节点的最大关键字。

B＋树的删除

B＋树中的关键字在叶节点层删除后，其在上层的副本可以保留，作为一个“分解关键字”存在。如果因为删除而造成节点中关键字数小于m/2−1，其处理过程与B−树的处理一样。

B*树

B*树是B＋树的变体，在B＋树的非根节点和非叶节点中再增加指向兄弟的指针。B*树定义了非叶节点关键字个数至少为（2/3）×m，B＋树则是（1/2）×m。

B＋树的分裂方法为，当一个节点满时，分配一个新的节点，并将原节点中1/2的数据复制到新节点，最后在父节点中增加新节点的指针。B＋树的分裂只影响原节点和父节点，而不会影响兄弟节点，所以它不需要指向兄弟的指针。

B*树的分裂方法为，当一个节点满时，如果它的下一个兄弟节点未满，那么将一部分数据移到兄弟节点中，再在原节点插入关键字，最后修改父节点中兄弟节点的关键字（因为兄弟节点的关键字范围改变了）；如果兄弟也满了，则在原节点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针。所以，B*树分配新节点的概率比B＋树要低，空间利用率更高。

对B树、B-树、B＋树和B*树的总结

B树：属于二叉树，每个节点只存储一个关键字，等于则命中，小于走左节点，大于走右节点。

B−树：属于多路搜索树，每个节点存储m/2−1到m−1个关键字，非叶节点存储指向关键字范围的子节点，所有关键字在整棵树中出现，且只出现一次，非叶节点可以命中。

B＋树：每个节点存储m/2到m个关键字，在B−树基础上，为叶子节点增加链表指针，所有关键字都在叶节点中出现，非叶节点作为叶节点的索引。B＋树总是到叶节点才命中。

B*树：在B＋树基础上，为非叶节点也增加链表指针，将节点的最低利用率从1/2提高到2/3。