Homework $6$

Indexes and Trees

Due $2/27/2024,$ Upload pdf to Canvas

$20$ pts

Records with the following values in a given attribute are being indexed on that attribute. The index takes these

values in in this order:

XNR AXA ZS$3$ NY$1$ S$85$ OY$9$ QWH AHZ $8$VD VPR $1$UQ QUX QBP TC$7$ IYT NNX

IX$]$

HHO

V$7$A U$8$I QXZ BWF DUN $1$YC $6$EM BWR

J$9$L

WTY

YHX

O$3$G

Consider a multi$-$level index with the above values, a B tree, that is well$-$constructed for these values where $p=$

$4$ and a leaf node is$,$ on average, $67\%$ full. Use your drawing program to draw the tree and show the parts of

each node.

a$.$ How many nodes are in the B tree given the records listed below?

b$.$ What is the first value shown in the $B$ tree?

c$.$ How many levels does this B tree have?

d$.$ What is the order in which a B tree will be traversed?

e$.$ When I search for the record with the value V$7$A$,$ how many block accesses will I make to reach the

record I need?

f$.$ At the node where you located the pointer to the record with $12V,$ how much had you reduced the

search space $($what percentage$)$ by using the B tree index?

Using the same values, consider a multi$-$level index, a $B^{+}$tree, that is well$-$constructed for these values where

$p($internal$)$ leaf