1) Complete the following table. x h(x) = (3x + 2) % 8 3 bits representation 2 0 000 13 9 3 5 21 15
Consider a relation ? with one attribute ?. Suppose you have to insert the following A = {2, 13, 9, 3, 5, 21, 15} into the relation ?. Construct a dynamic hash index on the attribute ? of ? based on extendable hashing.
Assume that the hash function used is ℎ(?) = (3? + 2)%8, where “%” is the modular operation and the hash function returns the remainder of (3? + 2) divided by 8. The value of ℎ(?) is in [0, 7] and hence we use a 3-bit binary integer to denote it in this
question (i.e., from 0002 to 1112).
In the hash index, a bucket keeps 2 entries, where an entry is a pair of search-key and pointer to the record in ? that has the key. Assume that the dynamic hash index has a bucket address table and an empty bucket of 0-bit initially as shown in Figure 1. During insertions, the maximum length of the hash prefix is limited to 2 bits. In other words, 3-bit prefixes are not allowed. Overflow buckets are used when necessary.
(1) Complete the following table.
| x | h(x) = (3x + 2) % 8 | 3 bits representation |
| 2 | 0 | 000 |
| 13 | ||
| 9 | ||
| 3 | ||
| 5 | ||
| 21 | ||
| 15 |
(2) Insert A into the relation ? in the given order, and show the dynamic hash index (the bucket address table and the buckets) after each insertion.
(3)Show the dynamic hash index after deleting 9.
(4) Repeat Question 3(2) using static hashing with the hash function ℎ(?) = (3? + 2)%7. A bucket keeps 2 entries, and overflow buckets are used when necessary. Show the static hash index after each insertion.
Step by step
Solved in 5 steps
