1
2
3
4
5
6
7
8
9
| - Lines 3–9: if the root node r is full, the root splits
and a new node s (having two children) becomes the root.
- Splitting the root is the only way to increase the height of a B-tree.
- *Unlike the slide, we preemptively split before insert*.
- The procedure finishes by calling `B-TREE-INSERT-NONFULL` to insert
key k into the tree rooted at the non-full root node.
- `B-TREE-INSERT-NONFULL` recurses as necessary down the tree,
at all times guaranteeing that the node to which it recurses is not
full by calling `B-TREE-SPLIT-CHILD` as necessary.
|
1
2
3
4
5
6
7
| - Lines 3–8 handle the case in which x is a leaf node by
inserting key k into x.
- If x is not a leaf node, then we must insert k into the appropriate
leaf node in the subtree rooted at internal node x.
- Lines 9–11 determine the child of x to which the recursion descends. Line 13 detects whether the recursion would descend to a full child, in which case line 14 uses `B-TREE-SPLIT-CHILD` to split that child into two non-full children, and lines 15–16 determine which of the two children is now the correct one to descend to.
- Lines 13–16 is to guarantee that the procedure never recurses to a full node.
- Line 17 then recurses to insert k into the appropriate subtree.
|
1
2
3
4
5
6
7
8
9
10
11
| - As the name suggested, this function split y, the child node of a node x.
- Node y originally has 2t children (2t - 1 keys) but is reduced to t children (t - 1 keys)
by this operation.
- Node z takes the t largest children (t - 1 keys) from y,and z becomes a new child of x,
positioned just after y in x's table of children. The median key of y moves up to become
the key in x that separates y and z.
- Lines 1–9 create node z and give it the largest t - 1 keys and corresponding
t children of y.
- Line 10 adjusts the key count for y.
- Lines 11–17 insert z as a child of x, move the median key from y up to x in order to
separate y from z, and adjust x's key count.
|
