Make your own free website on

Assignment 6

Exercise 18.2.1

Show the result of inserting the keys F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E in order into an empty B-tree with minimum degree 2. Only draw 2 configurations of the tree just before some node must split, also draw the final configuration.


We have t = 2, therefore the most a node can hold 2t 1 = 3 (node is full when number of key = 3) and the least t 1 = 1. And the insertion has to be in order of F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E.


Before the first split, after inserted F,S,Q






Before the second split, after inserted K,C










Before the third split, after inserted L,H,T,V








Before the fourth split, after inserted W















Before the fifth split, after inserted M,R,N















Before the sixth split, after inserted P,B,A,X















Before the seventh split, after inserted Y,D

















Final configuration, after inserted Z,E















Exercise 18.2-2

Explain under what circumstances, if any, redundant DISK-READ or DISK-WRITE operations are performed during the course of executing a call to B-TREE-INSERT. (A redundant DISL-READ is DISK-READ for a page that is already in memory. A redundant DISK-WRITE writes to disk a page of information that is identical to what is ready stored there.)


During a call to B-TREE-INSERT we can have a DISK-WRITE operation whenever the root node is changed. For example the insertion into a full node and the median key has to move up to the root node causing a change in root node.

DISK-READ operation can be omitted after the a B-TREE-SPLIT-CHILD function is performed recursively