Starting from the B$+$ tree shown in Figure $1,$ draw the tree that would result from the following operations.

Notes: $($i$)$ When a node is split into two nodes, ensure that the left node does not have fewer keys. $($ii$)$ When node merging or redistribution is needed, if both the left and right sibling nodes are available, use the left sibling node. $($iii$)$ You may skip drawing parts of the tree that do not change.

pt$.]$

$($a$)$ Staring from Figure $1,$ remove $2$ and $10.$

$($b$)$ Staring from Figure $1,$ insert $3.$

$($c$)$ Staring from Figure $1,$ remove $45,32,39,$ and $80.$

We need to build an index on a unique attribute that we expect to have $2000$ values. We are considering two options:

$($a$)$ A $B+$ tree index with $n=100.$

$($b$)$ A hash index with $100$ buckets that will uniformly distribute values in hash buckets.

Assume that each B$+$ tree node or hash bucket fits in and is stored as a disk block, and we can only load one disk block at a time into memory. How many disk blocks do we need to read in order to query and retrieve the corresponding tuple for a specific value? Discuss your answer for each of the above cases.

$[5$pt$.]$

Solve the following problems based on these assumptions. You must explain your calculations step by step.

Relation $R$ has $5**{10}^5$ tuples where each tuple occupies $200$ bytes.

Relation $S$ has ${10}^7$ tuples where each tuple occupies $50$ bytes.

The size of each disk block is $5KB.$

A file is stored as a consecutive set of disk blocks $($i$.$e$.,$ no file fragmentation$).$

We have $1MB$ of main memory available.

$1GB={10}^{3}MB={10}^{6}KB={10}^{9}B.$

$($a$)$ We want to use external sort$-$merge algorithm to sort $R.$ Explain how many initial runs will be created.

$($b$)$ Continuing with the previous problem, for the merging phase, we have decided to use $200KB$ as a buffer space for each input$/$output run. Explain how many merge passes are needed to obtain the final sorted run.