Make your own free website on Tripod.com

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.

Answer:

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

 

F Q S

 

 

 

Before the second split, after inserted K,C

C F K

 

S

 
 

 

 

 

 

 


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

F Q

 
 


 

 

 

 


Before the fourth split, after inserted W

F Q T

 

 

 

 

 

 

 

 


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

 

 

 

 

 

 


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

Q

 
 

 

 

 

 

 

 

 

 

 

 


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.)

Answer:

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