平时用的二叉排序树搜索元素的时间复杂度虽然是 $O(log_2n)$的, 但是底数还是太小, 树高太高.

0. 每个结点中包含有 n 个关键字信息： $(n,P_0,K_1,P_1,K_2,\ldots,K_n,P_n)$。其中：

a) $K_i$为关键字,且关键字按顺序升序排序 $K_{i-1}< K_i$

b) $P_i$ 为指向子树根的接点, $K_{i-1}<P(i-1) < Ki$

c) 关键字的数 n 满足(由此也确定了孩子结点的个数): $d-1\leqslant n \leqslant 2d-1$ (根节点可以少于d-1)

$h\leq \left\lfloor \log _{d}\left({\frac {n+1}{2}}\right)\right\rfloor .$

考虑到叶子结点如果有 2t-1 $(k_1,k_2,\ldots,k_{2t-1})$个 关键字, 则需要进行分裂,

一个有 2t-1$(k_1,k_2,\ldots,k_{2t-1})$个关键字 结点分裂是这样进行的: 此结点分裂为 两个关键字为 t-1个的结点, 分别为 $(k_1,k_2,\ldots,k_{t-1})$, $(k_{t+1},k_{t+2},\ldots,k_{2t-1})$, 然后再插入一个关键字$k_t$到父亲结点.

a. **旋转**: 如果其左右兄弟结点中存在关键字个数大于d-1 的结点,则从关键字个数大于 d-1 的兄弟结点中借关键字：**(这里看了网上的很多说法, 都是在介绍关键字的操作,而没有提到孩子结点. 我实现的时候想了很久才想出来: 借关键字时, 比如从右兄弟借一个关键字(第一个$k_1$), 此时即为左旋, 将父亲结点对应关键字移到当前结点, 再将右兄弟的移动父亲结点(因为要满足排序性质, 类似二叉树的选择) 然后进行孩子操作, 将右兄弟的$p_0$ 插入到 当前结点的孩子指针末尾) 左兄弟类似, <mark>而且要注意到边界条件, 比如当前结点是第0个/最后一个孩子, 则没有 左兄弟/右兄弟</mark>**)

2. 非叶子结点的子树指针 $p_i$指向关键字值属于 $[k_i,k_{i+1})$ 的子树（B- 树是开区间）；

$\Phi(H) = t(H) + 2m(h)$

结点的最大度数(即孩子数)$D(n)\leqslant \lfloor lgn \rfloor$, 证明放在最后

$O(1)$

摊还代价为$O(1)$

直接用 H.min, $O(1)$

易知 $\Delta \Phi = 0$

时间复杂度为$O(lgn)$ 即数组移动的长度, 而最多有 lgn个元素

$D(n)\leqslant \lfloor lgn \rfloor$