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
CS3402 Database Systems
Tutorials
CS3402 Tutorial 6 Solutions:
1.
512/8 = 64 blocks
Sequential search = 64/2 = 32 Binary search = log264 = log226 = 6
2.
(a) Static hashing with 5 buckets, each of which contains at most 3 records Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
3760
7115
NULL
4871
1821
NULL
4692
NULL
NULL
2369
5659
1074
NULL
CS3402 Database Systems
Tutorials
(b) Overflow handling Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
3. 8 hash codes (000, 001, 010, 100, 011, 110, 101, 111)
4.- When the number of key values in internal nodes is 3, a full internal node of
3760
7115
1620
3945
4759
NULL
6975
NULL
4871
1821
9206
NULL
4981
4692
NULL
2428
NULL
2369
5659
Overflow buckets
1074
this B+ tree will look like:
k1 k2 k3
– When the number of key value in leaf nodes is 3, a full leaf node of this B+ tree will look like:
k1
k2
k3
CS3402 Database Systems
Tutorials
– After inserting 2, 3, 5, the tree looks like
– After inserting 7, the tree looks like
3
– After inserting 11, 17, the tree looks like
37
– After inserting 19, 23, the tree looks like
3 7 17
– After inserting 29, 31, the tree looks like
17
37 23
2
3
5
2
3
5
7
2
3
5
7
11
17
11
17
2
3
5
7
19
23
2
3
5
7
11
17
19
23
29
31