B-树的应用以及添加和删除操作

B-树

B-树的应用

B-树适用于磁盘存储应用中。

因为磁盘操作相较于CPU读取操作比较费时，而B-树相较于二叉树来说，有更少的查找次数，效率更高。

用一个例子说明：
假如有1024个数据，用二叉树来存储的话，会有10层的树的高度。检索数据时从根节点到叶子节点是需要经过多次的数据比对操作。而在磁盘操作中每次对比后找下一个节点就是磁盘寻址。如果层比较高的话，就会寻找很多次。相对来说B-树的寻址次数会少很多。（因为一个节点包含了多个key值，总的来说会减少了树的高度）。

B-树的特点

一颗M阶B-树，满足以下条件(M阶是指该B-树是M叉树):

1. 每个节点至多拥有M颗子树
2. 根节点至少拥有两颗子树
3. 除了根节点以外，其余每个分支节点至少拥有M/2颗子树
4. 所有的叶子节点都在同一层上
5. 有k个子树的分支节点则存在k-1个关键字，关键字按照递增顺序进行排序
6. 根节点外，关键字数量满足ceil(M/2)-1 <= n <= M-1

分析一下这些条件:

如图是一个6阶B-树

条件1：比如（0012 0016 0022 0025 0028）这个节点，最多只能连6根线下去；

条件2比较好理解

条件3：就是每个分支节点必须要有3颗及以上的子树

条件4：叶子节点都在一层，保持绝对平衡。

条件5：比如（0003 0006）这个节点有2个关键字，它就有3个子树。因为有三个范围，分别对应三个子树。例如{x < 0003; 0003 < x < 0006; x > 0006}三个范围。

条件6：这个6阶B-树中，关键字的数量满足 2≤n≤5。

满足这6个条件就是B-树了。

B-树的操作

值的添加

B-树中值的添加涉及到分裂操作。因为当添加到一个节点的关键字数等于阶数时，就会通过分裂操作来满足B-树的性质。

还是以6阶B-树为例：

从（0001 0002 0003 0004 0005）该节点再添加0006关键字，

当节点超过5个key值时，会执行分裂操作。

值的删除

B-树中值的删除涉及到合并和借位操作。

以6阶B-树为例：

合并操作

删除0001关键字，

由于删除0001后，该节点只有0002一个关键字了，不满足条件6，因此需要合并操作。

借位操作

删除0002关键字，

由于删除0002后，该节点只有0003一个关键字了，这时候就借位根节点0006，将0007升级为根节点。