Question 6 (10 marks)
Consider a linear hashed file with the following properties
- initially with 2 (empty) pages in the file, d = 1, sp = 0
- able to hold up to 2 tuples per page
- an associated overflow file (initially empty, no pages)
- each page in the overflow file can also hold up to 2 tuples
A set of numeric keys (the numbers 1 to 32) are inserted into the file, in numeric order. Splits occur just before the insertion of the keys 6, 12, 18, 24, 30 The hash value of each key is simply the binary value of the number (e.g. hash(1) = 00000001, hash(15) = 00001111, and hash(21) = 00010101).
Show the state of the file(s) at the following points:
immediately before each split operation (before inserting the new value)
immediately after each split operation and after inserting the new value
The state should include:
- the pages of the data file, with tuples indicated by key values
- the depth of the file (d), the position of the split pointer (sp)
- any overflow pages, linked to their corresponding data pages by arrows
An abstract example (not using the above hash values) of what a state might look like:
[0] 1,2 -> 11,12
[1] 3,4
[2] 5,6 -> 13
[3] 7,8 -> 14,15 -> 16
[4] 9,10
d = 2 sp = 1
This is a sample just to show the format of states. It bears no relation to the hash values in this question.
Instructions:
- Type your answer to this question into the file called q6.txt
- Submit via: give cs9315 exam_q6 q6.txt
or via: Webcms3 > exams > Final Exam > Q6 submission > Make Submission
End of Question
Consider a linear hashed file with the following properties
- initially with 2 (empty) pages in the file, d = 1, sp = 0
- able to hold up to 2 tuples per page
- an associated overflow file (initially empty, no pages)
- each page in the overflow file can also hold up to 2 tuples
A set of numeric keys (the numbers 1 to 32) are inserted into the file, in numeric order. Splits occur just before the insertion of the keys 6, 12, 18, 24, 30 The hash value of each key is simply the binary value of the number (e.g. hash(1) = 00000001, hash(15) = 00001111, and hash(21) = 00010101).
Show the state of the file(s) at the following points:
immediately before each split operation (before inserting the new value)
immediately after each split operation and after inserting the new value
The state should include:
- the pages of the data file, with tuples indicated by key values
- the depth of the file (d), the position of the split pointer (sp)
- any overflow pages, linked to their corresponding data pages by arrows
An abstract example (not using the above hash values) of what a state might look like:
[0] 1,2 -> 11,12 [1] 3,4 [2] 5,6 -> 13 [3] 7,8 -> 14,15 -> 16 [4] 9,10 d = 2 sp = 1
This is a sample just to show the format of states. It bears no relation to the hash values in this question.
Instructions:
- Type your answer to this question into the file called q6.txt
- Submit via: give cs9315 exam_q6 q6.txt
or via: Webcms3 > exams > Final Exam > Q6 submission > Make Submission
