CS3402 Database Systems Tutorials
CS3402 Tutorial 7:
1. If the database consists of 512 records and the blocking factor is 8. On average, how many blocks needed to be searched to if the records are in unordered format and ordered format?
2. Suppose that we use hashing to organize a PRODUCT file containing records with the following product# values: 2369, 3760, 4692, 4871, 5659, 1821, 1074, and 7115.
(a) Let the hash function be h(product#) = product# mod 5, show the static hash
structure for this file. Assuming that each bucket can hold at most three records as shown below, and records in each bucket is unordered.
Bucket i
(b) Some new records are inserted into the file with product# values: 1620, 2428, 3945, 4759, 6975, 4981, and 9206. Show the updated hash structure for this file when using chaining for collision resolution. That is, if collision occurs, new records are inserted in overflow bucket and pointers are set from the original buckets to the overflow buckets. Assuming that each overflow bucket can hold at most three records, as shown below.
Overflow bucket
3. In extendible hashing, how many hash codes can you have in maximum if the global depth is 3?
4. Construct a B+ tree for the following set of key values: (2, 3, 5, 7, 11, 17, 19, 23, 29, 31)
Assuming that the tree is initially empty, values are added in ascending order, and the number of key values in internal nodes and leaf nodes are both 3.
pointer
pointer
pointer
pointer