B树（B_Tree）

#B树

M阶B树：即m叉树的一种特殊形式

#m叉树

树的构成和二叉排序树原理一样，但节点元素不止一个

每个节点都可以放置m-1个元素

每个节点都可以分出m个分支

#m阶B树

Pasted image 20260605212338.png

#B树的插入

核心要求：

==1.对于m阶B树，除根节点外，结合关键字个数\[m/2]-1<=n<=m-1==

2.子树0<关键字1<子树1<关键字2<子树2<...

插入步骤：

1.示例五阶B树。逐个插入四个元素后，根节点满员

Pasted image 20260605214227.png

爆满

Pasted image 20260605214356.png

2.满员后按照第\[m/2](向上取整)处的指针节点，即在虚线处分割根节点

Pasted image 20260605214437.png

以原来虚线右边的数字（49）作为新的根节点，将其余两个作为子树

3.继续插入数字，优先插入底部节点

Pasted image 20260605214805.png

Pasted image 20260605214849.png

-

满员后像上述类似，在虚线位置分割，虚线右边的88会进入父节点

Pasted image 20260605214941.png

继续插入数字，当底部某节点再次出现爆满情况时

Pasted image 20260605215101.png

依旧类似操作，80进入父节点，在父节点中占据指针节点的右边位置

Pasted image 20260605215232.png

如法炮制地插入数字，直到父节点满员

Pasted image 20260605215515.png

父节点爆满，此时再次分裂，依旧取虚线右边元素作为根节点，其余元素作为子树，并分别连接原来的子树

Pasted image 20260605215536.png

至此，所有插入情况讨论完毕

#B树的删除

依旧五阶B树为例,即下图删除

Pasted image 20260605220844.png

你要明白，写这个笔记，有点麻烦QAQ

1.删掉一个无关紧要的点，如60

Pasted image 20260605220944.png

说删就删没什么特殊的操作

要不，那啥，你去b站看回来吧QAQ

反正重点的核心要求一定要把握住，我去给他表个亮