B 树的运行时间上限
在计算机编程艺术中，第 485 页的底部
假设有一棵 m 阶 B 树，有 N 个键，因此 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)层节点有什么意义呢？
In the Art of Computer Programming, on the bottom of page 485
Suppose there's a B-tree of order m, and there are N keys, so the N+1 leaves appear on level l.
The numbers of nodes on levels 1,2,3... is at least 2,2[m/2],2[m/2]^2...
(Here [] denotes upper bound)
And Knuth give
N+1 >= 2[m/2]^(l-1)
My question is:
Shouldn't this be N+1 >= 2+2[m/2]+2[m/2]^2+...+2[m/2]^(l-1)?
What's the point of only taking nodes of the (l-1)th level into account?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
具有 k 个键的分支节点有 k + 1 个子节点。因此，无论级别 l - 1 上有多少节点，级别 l 上都必须有更多节点。
因此 N + 1（层 l 上的节点数）大于层 l 上的节点数 - 1。显然，实际情况级别 l - 1 上的节点数大于或等于级别 l - 1 上的最小节点数。因此 N+1≥ 2⌈米 / 2⌉l - 1。
A branch node with k keys has k + 1 children. So however many nodes there are on level l - 1, there must be more nodes on level l.
So N + 1 (the number of nodes on level l) is greater than the number of nodes on level l - 1. Obviously the actual number of nodes on level l - 1 is greater than or equal to the minimum number of nodes on level l - 1. So N + 1 ≥ 2⌈m / 2⌉l - 1.