B树
B树
数据库中数据量过大时，平衡二叉树由于深度过大，造成磁盘IO次数多，效率低。
B树也叫平衡多路查找树，它的出现就是为了减少磁盘IO操作，思想是降低树的高度，从==“瘦高”–>“矮胖”==。
核心是让每个节点承载更多的元素，拥有更多的孩子。
优点：改善数据库的查询效率，减少了对磁盘的IO操作次数
缺点：不便于范围查询
一个m阶的B树：单一节点拥有最多子节点的数量，称为B树的阶。
一个m阶B树的具有的特征（或必须满足的条件）
-
如果根节点不是叶子节点，那么它至少有两个节点。
-
所有叶子节点位于同一层(高度一致)。
-
除根节点和叶子节点之外，一个节点至少拥有
ceil( m / 2)个节点）。ceil() :向上取整，ceil(3/2)=ceil(1.5)=2 -
每个叶子节点包含
k-1个元素，ceil(m/2)<= k <=m。若m=3, 2<=k<=3, 1<=(k-1)<=2,也就是3阶的树叶子节点包含1~2个元素 -
拥有
k个节点的非叶子节点，包含k-1个元素。
B树的查找
如图是一颗3阶B树，满足B树的特征
查找元素5
第一步
第二步
第三步
找到节点中的元素5
B树插入元素(一定是在叶子节点插入)
1.插入后，没有破坏B树的规则
插入元素10。
插入10，并没有破坏B树的规则
2.插入后，叶子节点元素超过m-1个
叶子节点所能容纳的元素数为ceil(m/2)-1~(m-1)，超过m-1,会破坏B树的规则。
例如：插入元素4
对于3阶B树也就是叶子节点可以容纳1~2个元素，插入4后破坏 3阶B树规则，因此需要进行节点分裂。分裂后，将ceil(m/2)位置的元素上升到父节点。
这时，父节点(2,4,6)依旧是破坏B树规则，所以继续对父节点进行分裂
分裂到满足B树规则时，插入就完成了。
B树删除元素
1.删除叶子节点上的元素，没有破坏规则
删除元素3
叶子节点可以容纳1~2个元素，没有破坏规则。
2.删除叶子节点上的元素，剩余元素不足，破坏B树规则，但是相邻兄弟节点有多余元素
删除元素8
删除8后，（2,6)节点有两个节点，但是却有两个元素，不满足规则
拥有k个节点的非叶子节点，包含k-1个元素
- 为了不打破规则，我们向8的兄弟节点(3,5)借1个元素
不能直接将5放到8的位置，不符合平衡树的规则
需要先将借来的元素5上升到父节点中，再将5与8之间的元素6移动到原来8的位置
3.删除元素在叶子节点，剩余元素不足，破坏B树规则，相邻兄弟也没有多余元素
删除元素3
解决办法：相邻元素合并
4.删除的中间节点的元素
删除元素12
使用该元素的前驱(11)or后继(13)元素替换它的位置
- 前驱元素替换
由于除root和叶子节点外，一个节点拥有的节点数至少为ceil(3/2)=2，所以要将(3,5)此节点分为两个节点
- 后继元素替换
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/15591.html
