B树和B+树

B树

B树,又称作 m叉查找树

B树的定义

1. 除了根节点以外, 任何一个节点都 最多有$m-1$个元素
   最少有$\lceil m/2\rceil$ $-1$
   根节点只要求至少有一个元素,最多不能超过$m-1$个元素

这样比如一个5阶的B树,除了根节点外
每个节点内元素个数最少有2个,最多有4个
一个6阶的B树,除了根节点外
每个节点内元素个数最少有2个,最多有5个

2. 任何一个节点,所有子树的高度要相同(由这条性质可知,B树所有外部节点都在同一层上)

B树中非叶子节点的结构:

B树的高度计算

问题: 一个含有n个关键字的m阶B树,他的最大高度和最小高度是什么

计算高度时无特殊要求,叶子结点(即失败节点)那层是不计入高度的

含有n个关键字的m阶B树的最小高度计算

思路:如果要求高度最小,那么在关键字个数一定的情况下,我们希望这个B树的每个节点能够尽可能地装满
每个节点最多有$m-1$个元素和$m$个分叉
理想情况下:
第一层(只有根节点)元素个数为: $m-1$

第二层元素个数为: $m\ast (m-1)$ 即第一层有m个分叉指向第二层的m个节点,而第二层的m个节点最多有$m-1$个元素, 所以第二层最多有 $m\ast (m-1)$个元素

第三层元素个数为: $m\ast m\ast (m-1)$
… …
第h层的元素个数为: $1\ast m^{h-1}\ast (m-1)$

那么前h层的总个数是:
(m-1) * (1 + m + $m^2$ + $\cdots$ + $m^{h-1}$) = $(m-1)$ * $\frac{m^h-1}{m-1}$
即我们需要
(m-1) * $\frac{m^h-1}{m-1}$ $\ge$ $n$
解得
$h$ $\ge$ $lo{g}_m(n+1)$

含有n个关键字的m阶B树的最大高度计算

当求最大高度时,我们希望每一层的元素尽可能地少
第一层(只有根节点)最少元素数目为: 1个
第二层最少元素个数为: 1 * 2* ($\lceil$m/2$\rceil$-1) 个
… …
第h层最少元素个数为: 1 * 2 * ($\lceil$m/2$\rceil$)${}^{h-2}$ * ($\lceil$m/2$\rceil$ - 1)
可以推出,第h + 1层(即失败节点层)共有 1 * 2 * ($\lceil$m/2$\rceil$)${}^{h-1}$个节点
又因为,含有n个关键字的B树,必定有n+1个失败节点
所以
$n+1$ $\ge$ 1 * 2 * ($\lceil$m/2$\rceil$)${}^{h-1}$
解得
$h$ $\le$ $lo{g}_{\lceil m/2\rceil }\frac{(n+1)}{2}$ $+$ $1$

B树的操作

B树的插入操作

                                                           $\downarrow$ 插入25

                                                           $\downarrow$ 插入38

                                                           $\downarrow$ 插入49

                                                           $\downarrow$ 插入60



                                                           $\downarrow$ 插入80




                                                           $\downarrow$ 插入90



                                                           $\downarrow$ 插入88,99




                                                           $\downarrow$ 插入70 83 87



                                                           $\downarrow$ 继续不停插入,直到变成这种形式

B树的删除操作

B+树