B树和B+树_b树和b+树的区别

一、B树和B+树的区别：

B+树和B树相比，主要的不同点在以下3项：

• 所有关键码都存放在叶节点中，上层的非叶节点的关键码是其子树中最小（或最大）关键码的复写
• 叶节点包含了全部关键码及指向相应数据记录存放地址的指针，且叶节点本身按关键码从小到大顺序连接。如果按下层结点“最小关键码复写”原则，则树中每个非叶结点中有 m 棵子树必有 m - 1 个关键码；如果按下层结点“最大关键码复写”原则，则树中每个非叶结点中有 m 棵子树必有 m 个关键码
• 在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支。

根据B+树的结构，我们可以发现B+树相比于B树，在文件系统，数据库系统当中，更有优势，原因如下：

1. B+树的磁盘读写代价更低 
   B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。

2. B+树的查询效率更加稳定 
   由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3. B+树更有利于对数据库的扫描 
   B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能

二、B树

一棵m阶B树是一棵平衡的m路搜索树，它或者是空树，或者是满足下列性质的树：

• 根节点至少有两个子女
• 除根节点以外的所有节点（不包括失败节点）至少有[m/2]个子女
• 所有的失败节点都位于同一层

失败节点实际并不存在，指向它们的指针为空（与一般m路搜索树的不同之处）。

B树的搜索过程是一个在节点内搜索和循某一条路径向下一层搜索交替进行的过程。因此，B树的搜索时间和B树的阶m和B树的高度h直接有关，必须加以权衡。

在B树上搜索，搜索成功取决于关键码所在的层次，搜索不成功取决于树的高度。

 

1. 关键码个数N和树高的关系：

由B树的定义可知，如果h>1，根节点至少有两个子女，因此第二层上至少有两个节点。第二层上，每个节点至少有[ m / 2 ]个子女，因此第三层至少有2[ m/2 ]个节点，以此类推，h层上至少有 2 [ m/2 ] ^(h - 2) 个节点。位于第h-1层的失败节点至少有2 [ m/2 ] ^(h - 1)

N + 1 = 失败节点数 = 位于第 h + 1 层的节点数 >= 2[ m/2 ] ^ (h-1) ，则：

提高B树的阶数，可以减少树的高度，从而减少读入节点的次数，减少I/O次数。事实上，m受到内存可使用空间的限制。当m很大超出内存工作区容量时，节点不能一次读入到内存，增加了读盘次数，也增加了节点内搜索的难度。

2. B树的插入：

B树是从空树起，逐个插入关键码而生成的。在B树，每个非失败节点的关键码个数都在[ m/2 ] -1 到 m - 1 之间。插入是在某个叶节点开始的，该节点关键码个数多于 m - 1，则需要“分裂”。

完成一次插入操作时，最坏情况下，需要读写磁盘 3h + 1 次，当m较大时，平均 h+1 次。

搜索叶节点：h+1次，分裂非根节点，写 2(h - 1) 次（原结点和新生的兄弟结点），分裂根节点3次（多一个新的根节点）

 3. B树的删除：

首先找到目标关键码，如果所在节点不是叶节点，且被删关键码为Ki，1<= i <= n，则在删去该关键码后，应以该结点Pi所指示子树中的最小关键码x来代替被删关键码Ki所在的位置，然后在x所在的叶节点中删除x。现在，问题归结于在叶节点中删除关键码。

(1) 根节点（n >= 2)或者叶节点（n >= [ m/2 ]），直接删去并将修改后的结点写回磁盘

(2) 被删关键码所在叶节点删除前关键码个数 n = [ m/2 ] - 1，若此时与该结点相邻的右兄弟（右兄弟没有则左兄弟）结点的关键码个数 n >= [ m/2 ]，则可按一下步骤调整。

• 将父节点中刚刚大于（或小于）被删关键码的关键码Ki下移到刚刚被删关键码所在结点
• 将右兄弟（或左兄弟）结点中的最小（或最大）关键码上移到父节点位置
• 调整指针，兄弟结点移出关键码对应的指针平移到被删结点所在结点中，再填补、调整指针，将关键码个数减一

(3) 被删关键码所在叶节点删除前关键码个数 n = [ m/2 ] - 1，若这时与该节点相邻的右兄弟（或左兄弟）结点的关键码个数 n = [ m/2 ] - 1，则必须按以下步骤合并这两个结点。

• 将父节点p中相应关键码下移到选定保留的结点中。若要合并p中的子树 Pi 和 Pi+1 所指的结点，且保留Pi所指结点，则把p中的关键码 Ki+1 下移到Pi所指的结点中
• 把p中子树指针 Pi+1 所指结点中的全部指针和关键码都照搬到 Pi 所指结点后面。删去 Pi+1 所指结点。
• 在父节点p中用后面剩余的关键码和指针填补关键码 Ki+1 和指针 Pi+1
• 修改父节点p和选定保留节点的关键码个数。

最坏情况下读写磁盘 3h - 2 次，搜索关键码和填补关键码共 h 次读，重构过程中有h个结点要合并，读入 h - 1 个兄弟结点，最后把合并的 h - 1 个结点写回磁盘。

三、B+树

是一种B树的变形，在实现文件索引结构方面比B树使用得更普遍。

1. B+树的定义

1. 每个结点最多有m棵子树（子结点）
2. 根节点最少有一个子树，除根节点外，其他结点至少有 [ m/2 ] 个子树
3. 所有叶节点都在同一层，按从小到大的顺序存放全部关键码，各个叶节点顺序连接
4. 有n个子树的结点有n个关键码
5. 所有非叶节点可以看成是叶节点的索引，节点中关键码 Ki 与指向子树的指针 Pi 构成对子树（即下一层索引块）的索引项（Ki，Pi），Ki是子树中最大的关键码

通常B+树中有两个头指针：一个指向B+树根节点，另一个指向关键码最小的叶节点。 ->  可进行两种搜索运算：顺序搜索和自顶向下随机搜索。

2. B+树的插入

仅在叶节点上进行。每插入一个（关键码-指针）索引项之后都要判断结点中的索引项个数是否超出范围m。当插入后结点数 n > m，结点一分为二，个数为 floor( (m+1)/2 ) 和 ceil( (m+1)/2 )。

3. B+树的删除

和B树一致