数据结构之b树及其基本操作，b+树的基本概念

B树（B-tree）

B树是一种自平衡的树数据结构，它维护数据以支持一系列动态集合操作，如查找、顺序访问、插入、删除等。B树广泛应用于数据库和文件系统中，因为它能有效降低磁盘I/O操作的次数。

B树的特点：

1、所有值都是唯一的：在B树中，所有值都是唯一的，并且是按顺序存储的。
2、节点平衡：B树中的所有叶子节点都位于同一层，这使得B树保持平衡。
3、节点分裂和合并：当节点中的元素数量超过最大值或低于最小值时，节点会进行分裂或合并以维持平衡。
4、节点结构：
1.每个节点有m/2到m个子节点（m是B树的阶，一个节点最多可以有的子节点的数量），根节点除外，根节点至少有两个子节点（如果树不为空）。
2.每个节点包含n个关键字，其中m/2-1 ≤ n ≤ m-1。
3.节点中的关键字按升序排列。

B树的基本操作：

1、查找：从根节点开始，根据关键字比较结果向下遍历树，直到找到所需的节点或到达叶子节点。
2、插入：首先执行查找操作，如果关键字已存在则不插入；如果不存在，则在叶子节点中插入关键字，并可能需要向上调整树的结构以保持平衡。
3、删除：首先找到要删除的关键字所在的节点，然后删除它，并可能需要通过节点的合并或重新分配来维护树的平衡。

B+树

B+树是B树的一个变体，它被广泛用于数据库索引和文件系统中。B+树与B树的主要区别在于：

1、所有值都存储在叶子节点：在B+树中，所有的值都存储在叶子节点中，并且叶子节点之间通过指针相连，形成了一个有序的链表。这使得范围查询变得非常高效。
2、内部节点只存储关键字：内部节点（非叶子节点）仅存储关键字，用于指导搜索过程，但不存储实际的数据记录。
3、叶子节点包含所有关键字：叶子节点包含了B+树中所有的关键字，并按顺序存储。

B+树的这些特点使得它非常适合进行大量的范围查询操作，因为叶子节点之间通过指针相连，可以很容易地遍历整个数据集。同时，由于内部节点不存储数据，这使得B+树能够拥有更高的分支因子（即更多的子节点），从而减少树的高度，提高查询效率。