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