Quiz 1
CS525
Advanced Database Organization
数据库quiz代考 You have to hand in the assignment via blackboard .This is an individual and not a group assignment. Fraud will result in 0 points
Instructions
• You have to hand in the assignment via blackboard
• This is an individual and not a group assignment. Fraud will result in 0 points
• For your convenience the number of points for each part and questions are shown in parenthesis.
• There are 2 parts in this quiz
1. Disk Organization
2. Index Structures
Part 1.1 Disk Organization (Total: 18 Points) 数据库quiz代考
Question 1.1.1 Disk Access (18 Points)
Consider a disk with a sector size of 512 bytes, 2000 tracks per surface, 50 sectors per track, five double-sided platters, and average seek time of 10 msec. Suppose that a block size of 1024 bytes is chosen. Suppose that a file containing 100, 000 records of 100 bytes each is to be stored on such a disk and that no record is allowed to span two blocks.
[3 Points each]
1. What is the capacity of a track in bytes? What is the capacity of each surface? What is the capacity of the disk?
2. How many records fit onto a block?
3. How many blocks are required to store the entire file?
4. If the file is arranged sequentially on the disk, how many surfaces are needed?
5. How many records of 100 bytes each can be stored using this disk?
6. If pages are stored sequentially on disk, with page 1 on block 1 of track 1, what page is stored on block 1 of track 1 on the next disk surface?
Part 1.2 Index Structures (Total: 44 Points) 数据库quiz代考
Question 1.2.1 B
Create a B+-tree for table Item on key SSN. Assume that the tree is initially empty and values are added in the order shown in the table above. Construct B+-tree for the cases where the number of pointers that will fit in one node is as follows:
a. Three
b. Six 数据库quiz代考
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) 数据库quiz代考
Given is the B+-tree shown below (n = 3 ). Execute the following operations and write down the resulting B+-tree after each operation:
insert(3), delete(5), insert(10), insert(8), delete(29), delete(19), delete(11)
Use the conventions for splitting and merging introduced in the previous question.
Question 1.2.3 Extendable Hashing-tree Construction (14 Points)
Suppose that we are using extendable hashing on a file that contains records with the following search key values: 7, 15, 44, 11, 19, 3, 33, 17, 14, 43, 18, 20
Show the extendable hash structure for this file if the hash function is h(x)=x mod 7 and buckets can hold 2 records
