求助：修正向空B树依次插入1-20后根节点元素数的计算公式

首先明确定义：设N为根节点可容纳的最大元素数（对应B树阶数为m=N+1，每个非根节点最少有⌈(N+1)/2⌉-1个元素，最多N个元素）。

我们按插入阶段逐步推导：

阶段1：树高为1（仅根节点） #

• 当1 ≤ i ≤ N时，根节点未填满，元素数随插入次数递增：
  R(i) = i

阶段2：树高为2（根节点+子节点） #

• 插入第N+1个元素时，根节点满，分裂为1个根元素+2个半满子节点，此时R(N+1) = 1
• 每个子节点还可容纳N - ⌊N/2⌋ = ⌈N/2⌉个元素，两个子节点总共可接收2×⌈N/2⌉次插入。因此当N+1 < i ≤ N+1 + 2×⌈N/2⌉时，根节点元素数保持1不变：
  R(i) = 1
• 当i = N+1 + 2×⌈N/2⌉ + 1时，某个子节点满后分裂，将中间元素提升至根，此时根元素数变为2。后续每完成(k+1)×⌈N/2⌉次插入（k为当前根元素数），根元素数增加1，直到根元素数达到N，触发下一次根分裂。

通用递推逻辑 #

根节点元素数k对应的可插入元素范围：

• 当根有k个元素时，存在k+1个子节点，每个子节点最多可新增⌈N/2⌉个元素（从半满到满），因此总共可插入(k+1)×⌈N/2⌉个元素，期间根元素数保持k不变。
• 当插入次数耗尽该阶段的可插入量后，下一次插入会触发子节点分裂，将元素提升至根，根元素数变为k+1。
• 当根元素数达到N时，下一次插入会触发根分裂，树高加1，根元素数重置为1，进入下一轮树高的循环。

示例验证（以N=2，阶3 B树为例） #

• 1≤i≤2：R(i)=i（根元素1、2）
• i=3：根分裂，R(3)=1
• 4≤i≤4：子节点可插1个，R(4)=1
• i=5：子节点分裂提元素到根，R(5)=2
• 6≤i≤7：两个子节点各插1个，R(i)=2
• i=8：根满（2个元素），分裂后根元素1，树高3，R(8)=1

内容的提问来源于stack exchange，提问作者H-a-y-K