B-树和B+树

# B 树

# B 树的定义：

一颗 m 阶 B 树是一颗平衡的 m 路搜索树

# B 树的特性：

1. 每个结点至少两个子女

2. 每个非根节点包含的关键字个数 n：$\lceil m/2 \rceil - 1 \leq n \leq m-1$，

   每个非根节点子树个数 k：$\lceil m/2 \rceil \leq k \leq m$

3. 根节点的关键字个数 n：$1 \leq n \leq m-1$

   根节点的子树个数 k：$2 \leq n \leq m$

4. 所有的非终端结点中包含下列信息数据$(n，A_0，K_1,A_1,K_2,A_2,…,K_n,A_n)$

   • K_i是关键字，K_i < K_
   • $A_i$ 为指向子树根节点的指针，且指针$A_{i-1}$ 所指子树中所有结点的关键字均小于$K_i$
   • $A_n$ 所指子树中所有结点的关键字均大于$K_n$

5. 叶子结点都在同一层

6. 对于任一结点其子树高度相同

7. B 树的 m 值比树高大很多，m 的实用值一般在 100-500

# B 树的查找：

待查找元素$x_0$，如果：

1. $K_i < x < K_{i+1}(1 \leq i< n)$，准备查找$A_i$ 页
2. $x < K_1$，准备查找$A_0$ 页
3. $x > K_n$，准备查找$A_n$ 页

页内存储方式：顺序存储或者采用二叉排序树的形式

页内检索算法：顺序检索或者折半查找

# B 树的高度（不包括叶子结点）：

含 n 个关键字的 m 阶 B 树：

• 最小高度：

  让每个结点尽可能的满，每个结点有$m-1$ 个关键字，$m$ 个分叉，

  则 $n \leq (m-1)(1+m+m^2+m^3+...+m^{h-1})=m^h-1$，

  所以 $\color{red}h \geq log_m(n+1)$

• 最大高度：

  让各层分支尽可能少，即根节点有两个分支，其他节点只有$\lceil m/2\rceil$ 个分支

  各层节点至少有：

  第一层 1、第二层 2、第三层 $2\lceil m/2\rceil$、第三层 $2\lceil m/2\rceil^2 $ $......$

  第$h$ 层 $2\lceil m/2\rceil ^{h-2}$、第$h+1$ 层（即叶子节点 / 失败结点） 2\lceil m/2\rceil ^

  n 个关键字的 B 树一定有$n+1$ 个叶子结点，所以$n+1\geq 2\lceil m/2\rceil^{h-1}$，

  即$\color{red}h \leq log_{\lceil m/2\rceil} \frac{n+1}{2}+1$

# B 树的插入：