一、AOE网络相关计算

$$活动最早开始时间 = 活动起点到源点的最长路 \\\ 活动最晚开始时间 = 总的活动工期 - 活动尾端点到终点的最长路 - 活动时间$$

二、B树和B+树

相关定义

B树和B+树课上的讲义
$m$ 阶B树每个结点最多有 $m$ 个儿子，除根节点外，每个非终端结点的关键字个数大于等于 $\lceil \frac{m}{2} \rceil -1$，即每个非终端结点至少有$\lceil \frac{m}{2} \rceil$ 个子树。

课上讲到的B+树的定义和B树基本相同，即关键字个数比孩子节点个数少1：

各种资料上B+树的定义各有不同，一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。

而王道书上的关于B+树的定义则是关键字个数和孩子结点个数相同，这一点和B树有所区分，这里的定义方式也很好理解，B+树的定义本质上就相当于分块查找，每个父结点的关键字即为对应孩子节点的最大值。

B树高度的相关计算

含有 $n$ 个结点的 $m$阶B树高度的取值范围（B树高度一般不包括叶子结点，到终端结点即可）：
（1）最小高度：当B树中每个结点都被填满时，即每个结点都有m个孩子结点，此时整个树的高度取最小值。每个结点包含 $m-1$ 个关键字，当树高为 $h$ 时有： $$n \leq (m-1) (1 + m + m ^2 + m^3 + … + m^{h-1})$$
即： $$h \geq log_{m}n + 1$$
（2）最大高度：B树每个结点的关键字尽可能的少，根节点关键字最少为1，以后每层结点都至少有 $\lceil m / 2 \rceil$ 个分叉（孩子结点），即至少有 $\lceil m / 2 \rceil - 1$ 个关键字。
第一层结点个数为1， 第二层为 $2$，第三层为 $2\lceil m / 2 \rceil$，…… 第h层结点个数为 $2{}^{h-2}$，第h+1层的叶子节点个数为 .
又因为n个结点的B树必有n+1个叶子节点，因为n个结点的B树一定会整个区间划分为n+1个区间，相当于二叉排序树失败结点的个数，故当前B树一定有n+1个叶子结点吗，所以有：
$$n+1 \geq 2{\lceil m / 2 \rceil}^{h-1}$$
算得： $$h \leq 1 + \log_{\lceil m / 2 \rceil}{\frac{n+1}{2}}$$
综上所述： $$log_{m}n + 1 \leq h \leq 1 + \log_{\lceil m / 2 \rceil}{\frac{n+1}{2}}$$