Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 87
Текст из файла (страница 87)
(To split a full root, we will first make the root a child of a new emptyroot node, so that we can use B-TREE-SPLIT-CHILD. The tree thus grows in height by one;splitting is the only means by which the tree grows.)Figure 18.5 illustrates this process. The full node y is split about its median key S, which ismoved up into y's parent node x. Those keys in y that are greater than the median key areplaced in a new node z, which is made a new child of x.Figure 18.5: Splitting a node with t = 4.
Node y is split into two nodes, y and z, and themedian key S of y is moved up into y's parent.B-TREE-SPLIT-CHILD(x, i, y)1 z ← ALLOCATE-NODE()2 leaf[z] ← leaf[y]3 n[z] ← t - 14 for j ← 1 to t - 15do keyj[z] ← keyj+t[y]6 if not leaf [y]7then for j ← 1 to t8do cj[z] ← cj+t[y]9 n[y] ← t - 110 for j ← n[x] + 1 downto i + 111do cj+1[x] ← cj [x]12 ci+1[x] ← z13 for j ← n[x] downto i14do keyj+1[x] ← keyj[x]15 keyi[x] ← keyt[y]16 n[x] ← n[x] + 117 DISK-WRITE(y)1819DISK-WRITE(z)DISK-WRITE(x)B-TREE-SPLIT-CHILD works by straightforward "cutting and pasting." Here, y is the ithchild of x and is the node being split. Node y originally has 2t children (2t - 1 keys) but isreduced to t children (t - 1 keys) by this operation.
Node z "adopts" the t largest children (t - 1keys) of y, and z becomes a new child of x, positioned just after y in x's table of children. Themedian key of y moves up to become the key in x that separates y and z.Lines 1-8 create node z and give it the larger t - 1 keys and corresponding t children of y. Line9 adjusts the key count for y. Finally, lines 10-16 insert z as a child of x, move the median keyfrom y up to x in order to separate y from z, and adjust x's key count.
Lines 17-19 write out allmodified disk pages. The CPU time used by B-TREE-SPLIT-CHILD is Θ(t), due to the loopson lines 4-5 and 7-8. (The other loops run for O(t) iterations.) The procedure performs O(1)disk operations.Inserting a key into a B-tree in a single pass down the treeWe insert a key k into a B-tree T of height h in a single pass down the tree, requiring O(h)disk accesses. The CPU time required is O(th) = O(t logt n). The B-TREE-INSERT procedureuses B-TREE-SPLIT-CHILD to guarantee that the recursion never descends to a full node.B-TREE-INSERT(T, k)1 r ← root[T]2 if n[r] = 2t - 13then s ← ALLOCATE-NODE()4root[T] ← s5leaf[s] ← FALSE6n[s] ← 07c1[s] ← r8B-TREE-SPLIT-CHILD(s, 1, r)9B-TREE-INSERT-NONFULL(s, k)10else B-TREE-INSERT-NONFULL(r, k)Lines 3-9 handle the case in which the root node r is full: the root is split and a new node s(having two children) becomes the root.
Splitting the root is the only way to increase theheight of a B-tree. Figure 18.6 illustrates this case. Unlike a binary search tree, a B-treeincreases in height at the top instead of at the bottom. The procedure finishes by calling BTREE-INSERT-NONFULL to perform the insertion of key k in the tree rooted at the nonfullroot node.
B-TREE-INSERT-NONFULL recurses as necessary down the tree, at all timesguaranteeing that the node to which it recurses is not full by calling B-TREE-SPLIT-CHILDas necessary.Figure 18.6: Splitting the root with t = 4. Root node r is split in two, and a new root node s iscreated. The new root contains the median key of r and has the two halves of r as children.The B-tree grows in height by one when the root is split.The auxiliary recursive procedure B-TREE-INSERT-NONFULL inserts key k into node x,which is assumed to be nonfull when the procedure is called. The operation of B-TREEINSERT and the recursive operation of B-TREE-INSERT-NONFULL guarantee that thisassumption is true.B-TREE-INSERT-NONFULL(x, k)1 i ← n[x]2 if leaf[x]3then while i ≥ 1 and k < keyi[x]4do keyi+1[x] ← keyi[x]5i ← i - 16keyi+1[x] ← k7n[x] ← n[x] + 18DISK-WRITE(x)9else while i ≥ 1 and k < keyi[x]10do i ← i - 111i ← i + 112DISK-READ(ci[x])13if n[ci[x]] = 2t - 114then B-TREE-SPLIT-CHILD(x, i, ci[x])15if k> keyi[x]16then i ← i + 117B-TREE-INSERT-NONFULL(ci[x], k)The B-TREE-INSERT-NONFULL procedure works as follows.
Lines 3-8 handle the case inwhich x is a leaf node by inserting key k into x. If x is not a leaf node, then we must insert kinto the appropriate leaf node in the subtree rooted at internal node x. In this case, lines 9-11determine the child of x to which the recursion descends. Line 13 detects whether therecursion would descend to a full child, in which case line 14 uses B-TREE-SPLIT-CHILD tosplit that child into two nonfull children, and lines 15-16 determine which of the two childrenis now the correct one to descend to. (Note that there is no need for a DISK-READ(ci [x])after line 16 increments i, since the recursion will descend in this case to a child that was justcreated by B-TREE-SPLIT-CHILD.) The net effect of lines 13-16 is thus to guarantee that theprocedure never recurses to a full node.
Line 17 then recurses to insert k into the appropriatesubtree. Figure 18.7 illustrates the various cases of inserting into a B-tree.Figure 18.7: Inserting keys into a B-tree. The minimum degree t for this B-tree is 3, so a nodecan hold at most 5 keys. Nodes that are modified by the insertion process are lightly shaded.(a) The initial tree for this example. (b) The result of inserting B into the initial tree; this is asimple insertion into a leaf node.
(c) The result of inserting Q into the previous tree. The nodeRSTUV is split into two nodes containing RS and UV, the key T is moved up to the root, and Qis inserted in the leftmost of the two halves (the RS node). (d) The result of inserting L into theprevious tree. The root is split right away, since it is full, and the B-tree grows in height byone. Then L is inserted into the leaf containing JK. (e) The result of inserting F into theprevious tree. The node ABCDE is split before F is inserted into the rightmost of the twohalves (the DE node).The number of disk accesses performed by B-TREE-INSERT is O(h) for a B-tree of height h,since only O(1) DISK-READ and DISK-WRITE operations are performed between calls toB-TREE-INSERT-NONFULL.
The total CPU time used is O(th) = O(t logt n). Since BTREE-INSERT-NONFULL is tail-recursive, it can be alternatively implemented as a whileloop, demonstrating that the number of pages that need to be in main memory at any time isO(1).Exercises 18.2-1Show the results of inserting the keysF, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, Ein order into an empty B-tree with minimum degree 2. Only draw the configurations of thetree just before some node must split, and also draw the final configuration.Exercises 18.2-2Explain under what circumstances, if any, redundant DISK-READ or DISK-WRITEoperations are performed during the course of executing a call to B-TREE-INSERT.
(Aredundant DISK-READ is a DISK-READ for a page that is already in memory. A redundantDISK-WRITE writes to disk a page of information that is identical to what is already storedthere.)Exercises 18.2-3Explain how to find the minimum key stored in a B-tree and how to find the predecessor of agiven key stored in a B-tree.Exercises 18.2-4: ⋆Suppose that the keys {1, 2, ..., n} are inserted into an empty B-tree with minimum degree 2.How many nodes does the final B-tree have?Exercises 18.2-5Since leaf nodes require no pointers to children, they could conceivably use a different(larger) t value than internal nodes for the same disk page size.
Show how to modify theprocedures for creating and inserting into a B-tree to handle this variation.Exercises 18.2-6Suppose that B-TREE-SEARCH is implemented to use binary search rather than linear searchwithin each node. Show that this change makes the CPU time required O(lg n), independentlyof how t might be chosen as a function of n.Exercises 18.2-7Suppose that disk hardware allows us to choose the size of a disk page arbitrarily, but that thetime it takes to read the disk page is a + bt, where a and b are specified constants and t is theminimum degree for a B-tree using pages of the selected size. Describe how to choose t so asto minimize (approximately) the B-tree search time. Suggest an optimal value of t for the casein which a = 5 milliseconds and b = 10 microseconds.18.3 Deleting a key from a B-treeDeletion from a B-tree is analogous to insertion but a little more complicated, because a keymay be deleted from any node-not just a leaf-and deletion from an internal node requires thatthe node's children be rearranged.
As in insertion, we must guard against deletion producing atree whose structure violates the B-tree properties. Just as we had to ensure that a node didn'tget too big due to insertion, we must ensure that a node doesn't get too small during deletion(except that the root is allowed to have fewer than the minimum number t - 1 of keys, thoughit is not allowed to have more than the maximum number 2t - 1 of keys). Just as a simpleinsertion algorithm might have to back up if a node on the path to where the key was to beinserted was full, a simple approach to deletion might have to back up if a node (other thanthe root) along the path to where the key is to be deleted has the minimum number of keys.Assume that procedure B-TREE-DELETE is asked to delete the key k from the subtree rootedat x.
This procedure is structured to guarantee that whenever B-TREE-DELETE is calledrecursively on a node x, the number of keys in x is at least the minimum degree t. Note thatthis condition requires one more key than the minimum required by the usual B-treeconditions, so that sometimes a key may have to be moved into a child node before recursiondescends to that child.
This strengthened condition allows us to delete a key from the tree inone downward pass without having to "back up" (with one exception, which we'll explain).The following specification for deletion from a B-tree should be interpreted with theunderstanding that if it ever happens that the root node x becomes an internal node having nokeys (this situation can occur in cases 2c and 3b, below), then x is deleted and x's only childc1[x] becomes the new root of the tree, decreasing the height of the tree by one and preservingthe property that the root of the tree contains at least one key (unless the tree is empty).We sketch how deletion works instead of presenting the pseudocode. Figure 18.8 illustratesthe various cases of deleting keys from a B-tree.Figure 18.8: Deleting keys from a B-tree.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
