继续我们插入node2, 按照大小它被放在node3的左边, 同时树也不会被打破平衡
接着我们插入node12, 同样按照顺序它应该被插入在node14的左边, 但是此时,这个节点中又出现了三个元素, 又出现了4节点, 我们重新进行上溢出, 同样是找到 12 14 15 中间的14去和父节点node11进行合并,下图
用和上面相反的过程我们可以插入node1
同样插入s10这个节点, 同样我们会发现7,8,10三个元素在同一个节点上, 因此我们需要上溢, 然后8,11,14又在同一个节点上, 继续进行上溢, 然后得到下图
删除一个节点:
如果你想删除的节点在子节点上, 那么就直接进行删除
如果你想删除的节点在根节点行, 就找到这个根节点中这个元素的前驱或者后继,替换根节点中这个元素的位置,然后删除这个用来替换的叶子节点
比如我们想删除60这个节点
于是我们找到node60的前驱节点, 怎么找呢? 从node60开始,往左走一次, 然后往右走到头
如果我们想找到node60的后继节点怎么找呢? 从node60开始,往右走一步,然后往左走到头
实际上每次被删除的节点都是叶子节点
每次添加进来的元素,也必定在叶子节点上
underflow下溢
上溢的话,就是节点会往上走,下溢正好是相反的过程, 比如说,上树m=5, 即5阶的B树, 我们想删除上面的node22, 但是node22被删除后,就只剩下了node24, 这时候就违背了B树的定义, 每一个节点中至少要有 ⌈ m/2 ⌉ -1个元素,即 ⌈ 5/2 ⌉ -1 = 2 个元素
下溢节点中元素的数量必定是 ⌈ 5/2 ⌉ -2
情况1: 向兄弟节点借元素
我们在删除了根节点的右子树中的元素,直接导致了这个节点中的元素个数为 ⌈ m/2 ⌉ -2 , 但是B树中要求的是至少为 ⌈ m/2 ⌉ -1 , 我们就向它的兄弟节点借元素, 因为它的兄弟节点的元素个数比 最低要求还大1, 于是向下面这样变动,让根节点中间的元素,放到根节点右子节点的最左边, 根节点左节点的最右侧的元素放到根节点的中间位置, (注意为了不打破树的平衡,我们需要讲nodeT也倒换过去)
情况2: 兄弟节点不够 ⌈ m/2 ⌉ -1
进行元素的合并, 像下面这样,需要注意的地方就是此时父节点的元素中个数可能不足够 ⌈ m/2 ⌉ -1,因此我们重复这个过程
B树又称为多路搜索树, 是为不同的存储设备设计的平衡查找树,