- Things that you are not allowed to use
– Personal notes
– Printed lecture notes
- You are allowed to bring one page (both two sides can be used) of cheat sheet that must be turned in with the exam
- The exam is 75 minutes long
- For your convenience the number of points for each part and questions are shown in parenthesis.
- There are 2 parts in this exam (45 points total)
- Disk Organization (5)
- Index Structures (40)
Part 1 Disk Organization (Total: 5 Points)
Question 1.1 Disk Access (5 Points)
Consider a hard disk with the following specififications:
- 30, 000 RPM
- Average seek time 16ms
- Average of 800 sectors per track
(a) Based on the specififications, calculate the average rotational delay (in milliseconds) of this disk.
(b) Compute the average time to read a random sector from the disk.
Part 2 Index Structures (Total: 40 Points)
Question 2.1 B+ Operations (25 Points)
Consider a B + -tree whose nodes contain up to 4 keys. Execute the following operations and write down the resulting B + -tree after each step.
insert(150), insert(90), delete(100), delete(35), delete(10)
When splitting or merging nodes follow these conventions:
- Leaf Split: In case a leaf node needs to be split, the left node should get the extra key if the keys cannot be split evenly.
- Non-Leaf Split: In case a non-leaf node is split evenly, the “middle” value should be taken from the right node.
- Node Underflflow: In case of a node underflflow you should fifirst try to redistribute and only if this fails merge. Both approaches should prefer the left sibling.
Question 2.2 Hash Table Operations (15 Points)
Make the following assumptions:
- A bucket can hold two key-pointer pairs.
- The initial database D contains one object with key 00110.
Six objects with the following keys are inserted to D in the following order: 11010, 10011, 10110, 01010, 10100 and 01011.
- Assume that an extendible hash table is used to index the database. Show the index structure after each insertions. You have to show your work.