【数据结构】B树与B+树的联系与区别

 1. 概念

一棵m阶B树：

1. 树中每个结点至多有m棵子树。(即至多含有m-1个关键字，两颗子树指针夹着一个关键字)；
2. 若根结点不是终端结点，则至少有两颗子树。(至少一个关键字)；
3. 除根结点外的所有非叶子结点至少有[m/2]棵子树。(即至少含有[m/2]-1个关键字)；
4. 所有的叶子结点出现在同一个层次上，不带信息。(就像是折半查找判断树中查找失败的结点)。每一个结点中的关键字满足从左到右依次增大的规则。

B+树：

1. n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。
2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3. 所有的非终端结点可以看成是索引部分，结点中仅含其子树中的大（或小）关键字。
4. B+树中，数据对象的插入和删除仅在叶节点上进行。
5. B+树有2个头指针，一个是树的根节点，一个是小关键码的叶节点。

B树和B+树都是用于实现对磁盘数据的高效存取和索引的数据结构，它们的联系和区别如下：

2. 联系

1. B树和B+树都是多叉树。
2. B树和B+树的节点都可以存储多个数据项。
3. B树和B+树的查找、插入、删除操作都是基于节点的分裂与合并。

3. 区别

1. B树的节点既可以存储数据项，也可以存储子节点指针；而B+树的节点只存储数据项，所有子节点都通过指针连接在一起，形成一个有序链表。
2. 在B树中，数据项分散存储在各个节点中，因此在进行区间查找时，需要递归遍历所有可能包含目标数据的节点；而在B+树中，所有数据项都存储在叶子节点上，因此区间查找时只需要按照链表顺序遍历叶子节点即可，效率更高。
3. 在B树中，节点分裂后，新节点继承原节点的部分数据项和指针，因此节点分裂时需要重新平衡整个子树；而在B+树中，节点分裂后，新节点只继承原节点的数据项，因此不需要重新平衡整个子树，只需调整相邻节点的指针即可。
4. B树通常用于内存中的数据结构，而B+树通常用于磁盘文件系统、数据库等需要大规模存储数据的应用中。

综上所述，B+树相对于B树具有更高的查询效率、更高的存储利用率和更简单的维护方式，因此在实际应用中B+树被广泛使用。