B树

定义

大多数的查找树都是二叉树,这个可以理解,因为二叉树相对来说比较简单,易行,用递归方式编程也较易实现。这里介绍一种非二叉的树,即B树。

B数的性质

一个M阶的B树,应该具有以下的性质:

  • 根节点要么是叶子,要么具有2-M个子节点

  • 非叶节点(根节点除外)具有[M/2]-M个子节点

  • 所有的叶节点具有相同的深度

  • 所有的数据都存储在叶节点上

也就是说与二叉树不同,B树的非叶节点是不存储数据的,那么它存储什么呢?两个东西

  • 指向子节点的指针

  • 存储在叶节点中的数据的最小值。(第一个叶节点除外)

下图是一个4阶B树:
BTree

在这个4阶B树中,根节点有3个子节点,非根节点最多有4个节点(6,7,8,9),所有数据均位于叶节点(1-18),非叶节点存储的是指针和叶节点的最小值。

M阶B树的操作

对M阶B树的插入删除等操作最大要注意的是,要使操作完的树满足B树的约束条件

比如说,不能超过4个子节点,比如说我们要在9的后面插入9.5是不可以的,因为这违反了约束条件,因此我们要把它拆分,变成下图所示B树。
BTree1

当删除一个数据时,可以使相邻的兄弟节点合并,或者剥离一个相邻的兄弟节点并与之组成一个新的节点。

例如要删除节点9.5时,可以把数据9并入到前一个节点中,也可以在前一个节点中取一个值,组成新的结点,如下图所示

BTree2