我一直在slady.net上玩非常酷的 btree 小程序。我无法理解特定行为。看一下这个起始状态：
替代文字 http://www.freeimagehosting.net/uploads/db2931c7da.jpg
通过插入以下序列达到此特定状态：10、15、30、16、70、1、9、27、45、50、55。
我的问题是当我在序列中插入下一个值 65 时 [45, ] 节点会发生什么。
替代文字 http://www.freeimagehosting.net/uploads/3b70c1d302.jpg
[55,70] 节点将被 65 分割，作为中间值，65 将向上移动，然后也分割 [30,50] 节点。我的问题是：为什么 [45, ] 节点最终成为 [30, ] 节点的子节点？它的 parent 最初有 3 个孩子，最左边和最右边成为新的单独节点。45 介于这些值之间，似乎它也可以在 [65, ] 节点下结束......为什么？
一张图片胜过千言万语; 一部动画价值一百万：
http://constellationmedia.com/~funsite/static/btree-insert-animation.gif
这里要注意的关键是，当中心节点 50 被拉起时，它必须丢弃它的右孩子，因为它太低了。但是，65 需要一个新的左孩子，所以 50 将 45 交给 65。50 现在需要一个新的右孩子，并且包含 65 的节点需要成为孩子，所以它将新形成的 65 取而代之。
以下是 B-tree 插入规则的图解（其中最大节点大小为 4 个项目，5 个子节点）：
http://constellationmedia.com/~funsite/static/btree-insertion-rules.png
如果您要插入叶子（您首先要做的），xr则不会存在并且无关紧要。但是，如果你必须将一个节点一分为二，那么 newx就是你拉出的中心项，newxr是x.
将 45 节点作为第二个图中 65 节点的子节点是没有意义的，因为最右边的分支用于值 > 50（基于根节点的最右边的值） - 所以 45 必须进入中间分支某处。
每个节点总是有 n+1 个子节点，其中 n 是该节点中的键数。
在拆分之前，[30, 50] 节点有两个键和三个子节点，正如预期的那样。当你拆分它时，你最终会得到一个 [30, -] 节点和一个 [65, -] 节点（并将 50 提升一个级别）。
在下一层，您有（以前存在的）[16, 27] 和 [45, -]，以及新拆分的 [55, -] 和 [70, -] 节点。
您有两个父节点和四个子节点。每个父母必须有两个孩子，因为它只有一个钥匙。因此，给定排序规则，[45, -]必须是 [30, -] 的孩子，否则 (1) [30, -] 将没有足够的孩子，而 (2) [65, -] 将有太多的孩子。[编辑- 对于一个节点来说不是非法的太多，但分裂应该是平衡的]。
威尔 A 也是正确的。这是在拆分中间层节点时选择上推50键的结果，但这并不是真正的选择。拆分生成 [-, -] 和 [50, 65] 推高 30，或 [30, 50] 和 [-, -] 推高 65 将违反每个节点必须至少半满的规则。
