CS525 Advanced Database Organization Fall 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Quiz 1
CS525
Advanced Database Organization
Fall 2022
Part 1.1 Disk Organization (Total: 10 Points)
Question 1.1.1 Disk Access (10 Points)
Consider a disk with a sector size of 4096 bytes, 1000 tracks per surface, 50 sectors per track, five double-sided platters, and average seek time of 8 msec. Suppose that the disk platters rotate ate 7200 rpm. A block of 4096 bytes is chosen. Suppose that a file containing 150, 000 records of 100 bytes each is to be stored on such a disk and that no record is allowed to span two blocks. Also, no block can span two tracks.
1. How many records fit onto a block?
2. How many blocks are required to store the entire file? If the file is arranged sequentially on the disk, how many cylinders are needed?
3. How many records of 100 bytes each can be stored using this disk?
4. What time is required to read a file containing 100, 000 records of 100 bytes each sequentially? You can assume that the time for moving from one cylinder to another is very small.
Part 1.2 Index Structures (Total: 50 Points)
Question 1.2.1 B+ -tree Construction (10 Points)
Assume that you have the following table:
Item
SSN |
name |
age |
11 24 25 26 28 32 34 39 44 46 |
Pete Bob Heinz John Manny Gertrud Alice Lily Sammy Joe |
13 16 55 44 33 65 71 12 11 17 |
Create a B+ -tree for table Item on key age with n = 3 (up to three keys per node). Assume that the tree is initially empty and values are added in the order shown in the table above.
Write down the resulting B+ -tree after each step and when splitting or merging nodes follow these conventions:
• Leaf Split: In case a leaf node needs to be split during insertion and n is even, the left node should get the extra key. E.g, if n = 2 and we insert a key 4 into a node [1,5], then the resulting nodes should be [1,4] and [5]. For odd values of n we can always evenly split the keys between the two nodes. In both cases the value inserted into the parent is the smallest value of the right node.
• Non-Leaf Split: In case a non-leaf node needs to be split and n is odd, we cannot split the node evenly (one of the new nodes will have one more key). In this case the “middle” value inserted into the parent should be taken from the right node. E.g., if n = 3 and we have to split a non-leaf node [1,3,4,5], the resulting nodes would be [1,3] and [5]. The value inserted into the parent would be 4.
• Node Underflow: In case of a node underflow you should first try to redistribute values from a sibling and only if this fails merge the node with one of its siblings. Both approaches should prefer the left sibling. E.g., if we can borrow values from both the left and right sibling, you should borrow from the left one.
Question 1.2.2 Operations (20 Points)
Given is the B+ -tree shown below (n = 3 ). Execute the following operations and write down the resulting B+ -tree after each operation:
insert(9), insert(10), delete(2), insert(40), delete(29), delete(19)
Use the conventions for splitting and merging introduced in the previous question.
|
19 |
|
|
|
Question 1.2.3 Extensible Hash Construction (20 Points)
Suppose that we are using Extensible hashing on a file. Each bucket holds two keys. Execute the following operations
insert(4), insert(1), insert(7), insert(8), insert(6), insert(0), insert(2), insert(3)
and write down the resulting index after each operation. Assume the hash function is defined as:
x |
h(x) |
0 |
1101 |
1 |
0000 |
2 |
1010 |
3 |
1100 |
4 |
0001 |
5 |
0000 |
6 |
1010 |
7 |
0111 |
8 |
1110 |
2022-10-24