Sign in
Get StudyX it's free
Sign in
Open in AppQUESTION
Text
Image
DBMS - Linear Hashing Index Problem
Q3. Linear Hashing (20 points) For Question 3, assume the split policy used is splitting when inserting into an overflow page. Assume we initialize the Linear Hashing index as follows (the hash function used is given below the Linear Hashing index): Level $0, \mathrm{~N}=2$ $\mathrm{H}_{0}$ Next $=0$ 0 $20^{*}$ 1 \begin{tabular}{|l|l|} \hline $11^{*}$ & $13^{*}$ \\ \hline \end{tabular} $h_{i}($ value $)=h($ value $) \bmod (2 \mathrm{~N})$ 3.1) What is the minimum number of insertions needed such that the index structure has 4 buckets and is at Level $=1$ ? Give an example insertion sequence for your answer. 3.2) Draw what the index structure looks like after each of the following consecutive insertions. Remember to show the "next" pointer and level at each step: \[ 22=(10110)_{2}, 15=(1111)_{2}, 26=(11010)_{2}, 21=(10101)_{2}, 27=(11011)_{2} \text {. } \] Your answer should have 5 diagrams, with each one having taken into account all previous insertions. Assume that we use the same algorithm discussed in the lecture.
Q3. Linear Hashing (20 points) For Question 3, assume the split policy used is splitting when inserting into an overflow page. Assume we initialize the Linear Hashing index as follows (the hash function used is given below the Linear Hashing index): Level $0, \mathrm{~N}=2$ $\mathrm{H}_{0}$ Next $=0$ 0 $20^{*}$ 1 \begin{tabular}{|l|l|} \hline $11^{*}$ & $13^{*}$ \\ \hline \end{tabular} $h_{i}($ value $)=h($ value $) \bmod (2 \mathrm{~N})$ 3.1) What is the minimum number of insertions needed such that the index structure has 4 buckets and is at Level $=1$ ? Give an example insertion sequence for your answer. 3.2) Draw what the index structure looks like after each of the following consecutive insertions. Remember to show the "next" pointer and level at each step: \[ 22=(10110)_{2}, 15=(1111)_{2}, 26=(11010)_{2}, 21=(10101)_{2}, 27=(11011)_{2} \text {. } \] Your answer should have 5 diagrams, with each one having taken into account all previous insertions. Assume that we use the same algorithm discussed in the lecture.
Public Answer
7LQWTS The First Answerer
