[数据结构与算法]B树-多路平衡查找树

B树

数据库中数据量过大时，平衡二叉树由于深度过大，造成磁盘IO次数多，效率低。

B树也叫平衡多路查找树，它的出现就是为了减少磁盘IO操作，思想是降低树的高度，从==“瘦高”–>“矮胖”==。

核心是让每个节点承载更多的元素，拥有更多的孩子。

优点：改善数据库的查询效率，减少了对磁盘的IO操作次数
缺点：不便于范围查询

一个m阶的B树：单一节点拥有最多子节点的数量，称为B树的阶。

一个m阶B树的具有的特征（或必须满足的条件）

1. 如果根节点不是叶子节点，那么它至少有两个节点。

2. 所有叶子节点位于同一层(高度一致)。

3. 除根节点和叶子节点之外，一个节点至少拥有ceil( m / 2)个节点）。

   ceil() :向上取整，ceil(3/2)=ceil(1.5)=2

4. 每个叶子节点包含k-1个元素，ceil(m/2)<= k <=m 。

   若m=3, 2<=k<=3, 1<=(k-1)<=2,也就是3阶的树叶子节点包含1~2个元素

5. 拥有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)此节点分为两个节点
  

• 后继元素替换
  

阅读世界，共赴山海

423全民读书节，邀你共读