algorithm - b-tree的运行时间上限

Question

在计算机编程艺术中，在第 485 页的底部

假设有一棵m阶B树，有N个key，那么N+1个叶子出现在第l层。

级别 1,2,3... 上的节点数至少为 2,2[m/2],2[m/2]^2...

（这里 [] 表示上限）

和 Knuth 给

N+1 >= 2[m/2]^(l-1)

---

我的问题是：

这不应该是 N+1 >= 2+2[m/2]+2[m/2]^2+...+2[m/2]^(l-1) 吗？

只考虑第 (l-1) 级的节点有什么意义？

Answer 1

具有k个键的分支节点有k + 1 个子节点。因此，无论l - 1 层上有多少节点， l层上必须有更多节点。

所以N + 1（第 l 层的节点数）大于第l - 1 层的节点数。显然第l - 1 层的实际节点数大于或等于第 1 层的最小节点数l - 1. 所以N + 1 ≥ 2⌈<i>m / 2⌉<sup> l - 1。