Problem 1. Consider the following two B+trees for this problem.
50
50
30
70
10
30
50
10
20
30
50
60
70
(A)
(B)
Show the nal B+tree structure after we insert 60, 20, and 80 into Figure (a) in the given order.
Show the nal B+tree structure after we delete 20, 10, and 70 from Figure (b) in the given order.
Problem 2.
Consider a B+tree that indexes 300 records. Assume that n = 5 for this B+tree (i.e., each node has
at most 5 pointers), what is the minimum and maximum height (depth) of the tree? (A tree with only the root node has a height of 1.)
Problem 3. Consider the following key values: 106, 115, 916, 0, 96, 126, 16, 15, 31
These keys are to be inserted in the above order into an (initially empty) extendible hash table. The hash function h(n) for key n is h(n) = n mod 256; that is, the hash value is the remainder when the key value is divided by 256 (28). Thus, the hash value is an 8-bit value. Each block can hold 3 data items. Draw the extendible hash table after all data items are inserted. Show the keys themselves in the buckets, not the hash value. The bucket numbers are drawn from the bits at the high order end of the hash value. Be sure to indicate i for the directory, the number of hash value bits used. Also indicate i for each bucket, the number of hash function bits that are used for that bucket.
2
3
Problem 4. Answer Questions 1, 2, 3, and 4 below
In order to get partil credits when your answer is incorrect, please write down the formula that you used to obtain your answer.
Suppose you have 2 relations, R(A; B) and S(B; C), with the following characteristics:
The size of one disk block is 1000 bytes.
Attributes A, B are of length 10 bytes. Attribute C is of length 180 bytes. The tuples are not spanned across disk blocks
jRj = 5; 000 (number of tuples of R) jSj = 500 (number of tuples of S)
We have 30 blocks of memory bu er
We use one disk block for one B+tree node
Each pointer in a B+tree index (both a record pointer and a node pointer) uses 10 bytes.
(2 points) What is the minimum number of blocks needed to store R and S?
2. (2 points) We want to construct a dense B+tree on attribute B of table S by scan-ning the S table. What is the maximum possible n for the B+tree given the above parameters?
3. Assume the numbers computed in the previous problems. Assume that each node in the B+tree contains the minimum number of keys and pointers (as long as it is allowed in our parameter setting).
(4 points) How many nodes does the constructed B+tree have?
(4 points) How many disk IOs would be incurred during the construction of the B+tree on S.B? Assume that you use the main memory bu er in the most e - cient way to minimize the number of disk IOs. In your answer, please include the cost of reading the tuples from S and writing the constructed B+tree to the disk.
4. 4(4. points) How many disk IOs would have been incurred if we used block nested loop join? Is it worthwhile to construct an index on S.B to perform the join using the above algorithm considering the index construction overhead?
