B树和B+树

标签（空格分隔）：数据结构

参考/转载 : https://www.cnblogs.com/nullzx

1. B树

1.1 B树的定义

每个节点最多有m-1个关键字.
根节点最少有1个关键字.
非根节点最少有Math.ceil(m/2)-1个关键字.
每个根节点中的关键字都按照从小到大的顺序排列, 每个关键字的左子树中的所有关键字都小于它, 而右子树中的所有关键字节点都大于它.
所有叶子节点都位于同一层, 或者说根节点到每个叶子节点的长度都相同.

上图是一个阶数为4的B树, 在实际应用中的B树的阶数都非常大(通常大于100), 所以即使存储大量的数据, B树的高度依然会比较小, 每个节点中存储了关键字(Key)和关键字对应的数据(data), 以及孩子节点的指针. 我们将一个key何其对应的data成为一个记录, 但为了方便描述, 除非特别说明, 后续文中就采用key来代替(key,value)键值对这个整体. 在数据库中我们将B树(和B+树)作为索引结构, 可以加快查询速度, 此时B树中的key就代表键, 而data表示了这个键对应的条目在硬盘上的逻辑地址.

1.2 B树的插入操作

根据要插入的key的值, 找到叶子节点并插入.
判断当前节点的key的个数是否小于等于m-1, 若满足则结束, 否则进行第三步.
以根节点中间的key为中心分裂为左右两部分, 然后将这个中间的key插入到父节点中, 这个key的左子树指向分裂的左半部分, 这个key的右子树指向分裂后的右半部分, 然后将当前节点指向父节点, 继续进行第三步.

1.在空树中插入39.

2.继续插入22, 97和41 .

3.继续插入53.

4.依次插入13,21,40, 同样会造成分裂.

5.依次插入30,27,33; 36,35,34; 24,29. 结果如下图所示.

6.插入key值为26的记录, 插入后的结果如下图所示.

当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示。

进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。

分裂后当前结点指向新的根，此时无需调整。

1.3 B树的删除操作.

如果当前需要删除的key位于非叶子节点上, 则用后继key覆盖要删除的key, 然后在后继key所在的子支中删除该后继key. 此时后继key一定位于叶子节点上, 这个过程和二叉搜索树删除节点的方法类似. 删除这个记录后执行第2步.
该节点的key的个数大于等于Math.ceil(m/2)-1, 结束删除操作, 否则执行第三步.
如果兄弟节点key个树大于Math.ceil(m/2)-1, 则父节点中的key下移到该节点, 兄弟节点中的一个key上移, 删除操作结束.

下面以5阶B树为例, 介绍B树的删除操作, 5阶B树中, 节点最多有4个key, 最少有两个key

1.原始状态

2.在上面的B树中删除21, 删除后节点中的关键字个数依然大于等于2, 所以删除结束.

3.在上述情况下接着删除27, 从上图可知27位于非叶子节点中, 所以用27的后继替换它, 从图中可以看出27的后继为28, 我们用28替换27, 然后在28(原27)的有孩子节点中删除28, 删除后的结果如图.

删除之后发现, 当前小于2, 而它的兄弟节点中有三个记录(当前节点还有一个右兄弟节点, 选择右兄弟节点会出现合并节点的情况, 其实不论选择左右那个都行, 只是B树的形态会不一样而已.), 我们可以从兄弟节点中接取一个key, 所以父节点中的28下移, 兄弟节点中的26上移, 删除结束.

4.在上述情况下接着32, 结果如下图

5.上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。

同理，对于当前结点而言只能继续合并了，最后结果如下所示。

合并后结点当前结点满足条件，删除结束。

2. B+ 树

2.1 B+树的定义

除此之外B+树还有以下要求:

B+树包含两种类型的节点: 内部节点(也称为索引节点)和叶子节点. 根节点本身既可以是内部节点, 也可以是叶子节点. 根节点的关键字个数最少可以只有一个.
B+树和B树最大的不同是内部节点不保存数据, 只用于索引, 所有数据(或者说是记录)都保存在叶子节点中.
m阶B+树表示了内部节点(索引节点)最多有m-1个关键字(或者说内部节点最多有m个子树), 阶数m同时限制了叶子节点最多存储m-1个记录.
内部节点中的key都按照从小到大的顺序排列, 对于内部节点中的一个key,左树中所有的key都小于它, 右子树中的key都大于等于它. 叶子节点中的记录也按照key的大小排列.
每个叶子节点都存有相邻叶子节点的指针, 叶子节点本身依关键字的大小自小而大的顺序链接.

2.2 B+树的插入操作

若为空树, 创建一个叶子节点, 然后将记录插入其中, 此时这个叶子节点也是根节点, 插入操作结束.
针对叶子类型节点: 根据key值找到叶子节点, 向这个叶子节点插入记录。插入后，若当前结点key的个数小于等于m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

1.空树中插入5

2.一次插入8, 10, 15

3.插入16

当然我们还有另一种分裂方式, 给左节点三个记录, 右节点两个记录,此时索引节点中的key就变为15.

4.插入17

5.插入18, 插入之后如下图所示.

当前节点的关键字个数大于5, 进行分裂. 分裂成两个节点, 左节点两个记录, 右节点三个记录, 关键字16进位到父节点(索引类型)中, 将当前节点的指针指向父节点.

6.插入若干条数据后

7.在上图中插入7, 结果如下图所示.

当前结点的关键字个数超过4，需要分裂。左结点2个记录，右结点3个记录。分裂后关键字7进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。

当前节点的关键字个数超过4, 需要继续分裂, 左节点两个关键字, 右节点三个关键字, 关键字16进入到父节点中, 将当前节点指向父节点, 结果如下图所示.

2.3 B+树的删除操作

如果叶子节点中没有相应的key, 则删除失败. 否则执行下面的步骤.

删除叶子节点中对应的key. 删除后若节点的key的个数大于等于Math.ceil(m-1)/2 - 1, 删除操作结束, 否则执行第二步.
若兄弟节点key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行第3步。
若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第4步（第4步以后的操作和B树就完全一样了，主要是为了更新索引结点）。
若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1，则删除操作结束。否则执行第5步.
若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步
当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。

1.初始状态

2.删除22, 删除后结果如下图.

删除后叶子结点中key的个数大于等于2，删除结束

3.删除15, 删除后的结果如下图所示.

删除后当前结点只有一个key,不满足条件，而兄弟结点有三个key，可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9，删除结束。

4.删除7，删除后的结果如下图所示.

当前结点关键字个数小于2，（左）兄弟结点中的也没有富余的关键字（当前结点还有个右兄弟，不过选择任意一个进行分析就可以了，这里我们选择了左边的），所以当前结点和兄弟结点合并，并删除父结点中的key，当前结点指向父结点。

此时当前结点的关键字个数小于2，兄弟结点的关键字也没有富余，所以父结点中的关键字下移，和两个孩子结点合并，结果如下图所示。