COMP$3278$B Introduction to Database Management Systems

Assignment $4$

Storage and Indexing

$[20\%]$ Consider the following B$+-$tree. Insert the keys $1,17,89,42,74$

in it in order. Show the tree after each insertion operation.

If a non$-$leaf node contains $x$ pointers and splitting is needed,

distribute the ${|}_{{?}_{?}}\frac{x}{2_{{?}_{?}}}|$ pointers to the node on left and $|$~$\frac{x}{2}$~$|$

pointers to the node on right.

$[20\%]$ Consider the following B$+-$tree. Delete the keys $99,82,73,69$ from it in order. Show

the tree after each deletion operation.

Assume that if merging or redistribution of a node is necessary, it's left sibling, if

exists, is used first.