计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】-Toy模板网

这篇具有很好参考价值的文章主要介绍了计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

B树(B-Tree)

B树（B-Tree）是一种自平衡的搜索树，又称平衡多路查找树，主要用于系统中大量数据的读和写操作。B树的特点是能保持数据有序，这使得在B树中进行查找、顺序访问、插入和删除等操作都非常高效。

B树中单一节点拥有的最多子结点的数量称为B树的阶，一个m阶B树的主要特点如下：

所有叶子节点都在同一层

每个节点中的元素都按照升序排列，每个元素的左子树中的所有关键字都小于它，右子树中所有元素都大于它

若根节点不是叶子节点，则至少有两颗子树（2<=子树个数<=m）

除根结点和叶子节点外，节点至少有ceil(m/2)棵子树

有k个孩子的非叶子节点包含k-1个元素（ceil(m/2)<=k<=m，当m=3时，2<=k<=3）

在B树中，插入和删除操作可能涉及节点的分裂和合并，以保持树的平衡性。当插入数据时，如果节点已满，会触发节点的分裂操作；当删除数据时，如果节点过于空闲，会触发节点的合并操作。

B树的查询操作

计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】,计算机基础,# 数据结构,数据结构,b树,B+树

上图是一个三阶的B树，如果我们要查找元素5，需要进行如下步骤

与根节点元素9进行比较，5<9进入左子树
与左子树元素2和6进行比较，发现2<5<6，进入中间子树
与中间子树3和5进行比较，找到5

B树的几种插入删除情况

计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】,计算机基础,# 数据结构,数据结构,b树,B+树

如果插入10，没有打破规则，直接插入

计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】,计算机基础,# 数据结构,数据结构,b树,B+树

如果插入4，这时候可以看到叶子节点元素过多，超过了m-1，因此需要对节点进行分裂
将ceil(m/2)位置的元素上升到父结点
此时父结点的元素个数同样不满足B树规则，因此继续对父结点进行分裂

计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】,计算机基础,# 数据结构,数据结构,b树,B+树

删除元素13，没有改变规则

计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】,计算机基础,# 数据结构,数据结构,b树,B+树

删除元素8，剩余元素不足，相邻的兄弟节点没有多余元素，这时候就需要与相邻兄弟节点进行合并操作
首先移动父结点中的元素【该元素在两个需要合并的两个结点元素之间】下移到其子结点中，然后将这两个结点进行合并成一个结点
删除元素11，剩余元素不足，相邻兄弟节点有多余元素
删除后，父节点（9，12）就少一个子节点。此时可以向兄弟节点“借”一个元素。但6不可以直接放在元素11的位置，需要上升到到父节点中，再把元素6和12之间的元素9移动到元素11的位置

计算机基础---＞数据结构（8）【B树、B+树＜超详细图文＞】,计算机基础,# 数据结构,数据结构,b树,B+树