The Chinese University of Hong Kong
Department of Systems Engineering and Engineering Management
SEEM3550A Fundamentals of Information Systems
2023-24 Assignment 2: Indexing/Hashing
This is an individual assignment. Every onemust submit it individually1. This assignment
is for understanding indexing and hashing, which is worth of 10% of the total assessment.
The due date for the assignment 2 is 17:00, April 9, 2024. Submissions need to be submitted
to the online Blackboard system. The late penalty will be 10% per day. A submission will
not be accepted five days after the deadline.
In the website for the textbook https://www.db-book.com/Practice-Exercises/index-
solu.html, the solutions to practice exercises in most chapters are given. It is strongly
recommended for you to try the practice exercises and see whether your answers are correct
by checking the answers provided at the website. It will indeed help you to understand the
course materials.
■ Q1. [38 marks] Consider a relation with one attribute. Suppose you have to insert the
followingA = {10, 20, 30, 40, 25, 50, 32, 60, 28, 23} into the relation . Construct a B+-tree
on the attribute of . Following the pseudocode of B+-tree given in the textbook (or the
slides in ch11.ppt), construct a B+-tree with = 3. Assume that the B+-tree is initially
empty.
(1) [30 marks] Given A, insert the key values in such an order, and show the B+-tree
after every insertion.
(2) [4 marks] Given the B+-tree constructed in the step (1), show how the B+-tree is
changed step-by-step following the pseudo-code when the key value “50” is deleted.
(3) [4 marks] Given the B+-tree constructed in the step (2), show how the B+-tree is
changed step-by-step following the pseudo-code when the key value “25” is deleted.
■ Q2. [12 marks]
(1) [4 marks] Assume = 2 in the B+-tree, and there are 256 search-key values in the
file, what is the number of leaf nodes in the B+-tree?
1Departmental Guideline for Plagiarism (Department of Systems Engineering and Engineering Management):
If a student is found plagiarizing, his/her case will be reported to the Department Examination Panel. If the
case is proven after deliberation, the student will automatically fail the course in which he/she committed
plagiarism. The definition of plagiarism includes copying of the whole or parts of written assignments,
programming exercises, reports, quiz papers, mid-term examinations and final examinations. The penalty will
apply to both the one who copies the work and the one whose work is being copied, unless the latter can
prove his/her work has been copied unwittingly. Furthermore, inclusion of others’ works or results without
citation in assignments and reports is also regarded as plagiarism with similar penalty to the offender. A
student caught plagiarizing during tests or examinations will be reported to the Faculty office and appropriate
disciplinary authorities for further action, in addition to failing the course.
2(2) [4 marks] Assume = 7 in the B+-tree, and there are 256 search-key values in the
file, what is the upper bound of the tree height in theory?
(3) [4 marks] Explain which one is a good design: Construct a B+-tree with = 2 and
construct a B+-tree with = 7. Justify your answer from the perspectives of search
efficiency, index maintenance, and index space complexity.
■ Q3. [50 marks] Consider a relation with one attribute . Suppose you have to insert
the following A = {15, 19, 12, 82, 95, 31, 9} into the relation . Construct a dynamic hash
index on the attribute of based on extendable hashing.
Assume that the hash function used is ℎ() = (3 + 1)%8, where “%” is the modular
operation and the hash function returns the remainder of 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 Fig. 1. Overflow
buckets are used when necessary.
0 bit Hash Prefix
0 bit Bucket
Fig. 1. Initial state of the hash index.
(1) [12 marks] Complete the following table.
k h(k) = (3k+1) % 8 3 bits representation
15 6 110
19
12
82
95
31
9
(2) [18 marks] 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) [3 marks] Show the dynamic hash index after deleting 82.
(4) [3 marks] Based on the results of Q3(3), show the dynamic hash index after deleting
15.
(5) [14 marks] Repeat Question Q3(2) using static hashing with the hash function
ℎ() = %8. A bucket keeps 2 entries, and overflow buckets are used when necessary.
Show the static hash index after each insertion.