Let's think about the worst$-$case scenario $($making the tree highest$)$ for a B$-$tree.

That means the root has $2$ children and each internal node has $|$~$\frac{M}{2}$~$|$ children. The following tree shows the worst case scenario where $M=5.$

$14.$ Think about the worst$-$case B$-$tree where $M=5$ as shown below. Figure out how many nodes we have at each level in the following tree. HINT: check page $3$ of lec notes "Notes$-9$A multiway"

Level# # of nodes at each level $($count Xs$)$

$L=$

$1$

$L=$

$L=$

$L=$

$15.$ Think about the worst$-$case $B-$tree with $M=7.$

a$)$ How many children does each internal node have?

b$)$ Now draw a worst$-$case B$-$tree from $L=0$ to $3.$ Also count the number of nodes you have at each level, $L=0$ to $3.$ Then come up with the general formula that works for $L1$ that tells us the total number of nodes at Level $L,$ where $N$ is the total number of nodes $($not keys$/$elements$)$ in the tree.General formula for L$>=1$ using M and L$16.$ Do the same as #$15$ for a worst$-$case B$-$tree with M$=9.$