B-树和B+树
B树
B树的定义：
一颗m阶B树是一颗平衡的m路搜索树
B树的特性：
每个结点至少两个子女
每个非根节点包含的关键字个数n：\(\lceil m/2 \rceil - 1 \leq n \leq m-1\)，
每个非根节点子树个数k：\(\lceil m/2 \rceil \leq k \leq m\)
根节点的关键字个数n：\(1 \leq n \leq m-1\)
根节点的子树个数k：\(2 \leq n \leq m\)
所有的非终端结点中包含下列信息数据\((n，A_0，K_1,A_1,K_2,A_2,…,K_n,A_n)\)
- \(K_i是关键字，K_i < K_{i+1}\)
- \(A_i\)为指向子树根节点的指针，且指针\(A_{i-1}\)所指子树中所有结点的关键字均小于\(K_i\)
- \(A_n\)所指子树中所有结点的关键字均大于\(K_n\)
叶子结点都在同一层
对于任一结点其子树高度相同
B树的m值比树高大很多，m的实用值一般在100-500
B树的查找：
待查找元素\(x_0\)，如果：
- \(K_i < x < K_{i+1}(1 \leq i< n)\)，准备查找\(A_i\)页
- \(x < K_1\)，准备查找\(A_0\)页
- \(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\)、第三层 $2m/2^2 $ \(......\)
第\(h\)层 \(2\lceil m/2\rceil ^{h-2}\)、第\(h+1\)层（即叶子节点/失败结点） \(2\lceil m/2\rceil ^{h-1}\)
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\)
