我一直在 slady.net 上玩非常酷的 btree 小程序。我无法理解特定行为。看看这个起始状态：
alt text http://www.freeimagehosting.net/uploads/ db2931c7da.jpg
这个特定的状态是通过插入以下序列达到的：10, 15, 30, 16, 70, 1, 9, 27, 45, 50, 55。
我的问题是关于 [ 发生了什么45, ] 节点，当我在序列中插入下一个值时，65。
alt text http:// www.freeimagehosting.net/uploads/3b70c1d302.jpg
[55,70] 节点将被 65 分割，作为中间值，65 将向上移动，然后分割 [30,50]节点也是如此。我的问题是：为什么 [45, ] 节点最终成为 [30, ] 节点的子节点？它的父节点最初有 3 个子节点，最左边和最右边成为新的独立节点。 45 位于这些值之间，看起来它也可能最终位于 [65, ] 节点下......为什么？
I have been playing with the very cool btree applet at slady.net. I'm having trouble understanding a particular behavior. Take a look at this starting state:
alt text http://www.freeimagehosting.net/uploads/db2931c7da.jpg
This particular state was arrived at by inserting the following sequence: 10, 15, 30, 16, 70, 1, 9, 27, 45, 50, 55.
My question is regarding what happens to the [45, ] node when I insert the next value in the sequence, 65.
alt text http://www.freeimagehosting.net/uploads/3b70c1d302.jpg
The [55,70] node will be split by the 65, and being the middle value, the 65 will travel back up and then split the [30,50] node as well. My question is: Why does the [45, ] node end up a child of the [30, ] node? It's parent originally had 3 children, the left most and the right most became new seperate nodes. The 45 was between those values and it seems like it could have ended up under the [65, ] node just as well... Why?
发布评论
评论（3）
一图胜千言；动画价值一百万：
http://constellationmedia.com/~funsite /static/btree-insert-animation.gif
这里要注意的关键是，当中心节点 50 被拉起时，它必须丢弃其右子节点，因为它太靠下了。然而，65 需要一个新的左子节点，因此 50 将 45 移交给 65。50 现在需要一个新的右子节点，并且包含 65 的节点需要创建子节点，因此它将新形成的 65 代替。
以下是 B 树插入规则的说明（其中最大节点大小为 4 个项目，5 个子节点）：
http://constellationmedia.com/~funsite/static/btree-insertion-rules.png
xr将不存在，并且无关紧要，如果您'重新插入一片叶子（这是你首先要做的）。但是，如果您必须将一个节点分成两半，则新的x是您拉出的中心项，而新的xr是x 的右子节点。A picture is worth a thousand words; an animation is worth a million:
http://constellationmedia.com/~funsite/static/btree-insert-animation.gif
The key thing to notice here is that when the center node 50 is pulled up, it has to throw away its right child because it's too far down. However, 65 needs a new left child, so 50 hands 45 over to 65. 50 now needs a new right child, and the node containing 65 needs to be childed, so it takes the newly formed 65 in its place.
Here are illustrated B-tree insertion rules (where maximum node size is 4 items, 5 child nodes):
http://constellationmedia.com/~funsite/static/btree-insertion-rules.png
The
xrwon't exist and won't matter if you're inserting into a leaf (which you do first). However, if you have to split a node in half, the newxis the center item you pulled out, and the newxris the right child ofx.在第二个图中，45 节点作为 65 节点的子节点是没有意义的，因为最右边的分支适用于值 > 。 50（基于根节点最右边的值） - 所以 45 必须进入中间分支的某个地方。
It makes no sense for the 45 node to be a child of the 65 node in the second diagram as the rightmost branch is for values > 50 (based on the root node's right-most value) - so 45 has to go into the middle branch somewhere.
每个节点始终有 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 将违反每个节点必须至少半满的规则。
Each node always has n+1 children, where n is the number of keys in that node.
Before splitting, the [30, 50] node has two keys and three children, as expected. When you split that, you end up with a [30, -] node and a [65, -] node (and push the 50 up a level).
At the next level down, you have the (previously existing) [16, 27] and [45, -], and the newly-split [55, -] and [70, -] nodes.
You have two parent nodes and four children. Each parent must have two children because it has a single key. Therefore, given the ordering rules, [45, -] must be a child of [30, -] because otherwise (1) [30, -] wouldn't have enough children, and (2) [65, -] would have too many children. [EDIT - not illegally too many for a node, but the split is supposed to be balanced].
Will A is also correct. This is a consequence of choosing to push up the 50 key when splitting the middle-layer node, but this wasn't really a choice. Splitting to either produce [-, -] and [50, 65] pushing up 30, or [30, 50] and [-, -] pushing up 65 would violate the rule that every node must be at least half full.