Question $1$: $[30$ points$]$ Indexing and Sorting a$)[6$ points$]$ Consider a

B$+$

$-$tree with a maximum fanout of $64$ for both the leaf and the non$-$leaf nodes. If you are told that the average occupancy of each node in this tree is

$50\%$

$,$ then calculate the number of entries in the index for a tree of height $3,$ i$.$e$.$ there is root level, two non$-$leaf levels below the root, and then the leaf level. b$)[4$ points$]$ Draw the final

B$+$

tree after inserting a key with value $11$ in the

B$+$

$-$tree shown below. Assume that the insertion algorithm does not allow any redistribution. The order of the tree below is $2.$