CS5481 Data Engineering Assignment 1
Common mistakes
1.
Misunderstood the meaning of K, which is the number of search-key values in the file, NOT the number of search-key values in the whole tree.
Failed to consider some special cases, such as h=1.
Failed to consider the general cases.
Failed to formulate the relationship between h and K accurately.
2.
Failed to rebuild the B+-tree correctly such as using bottom-up construction in a wrong way.
Failed to follow the course conventions for insertion and deletion.
Failed to provide steps to arrive at the final result.
3.
Failed to provide steps to arrive at the final result.
Failed to follow the course convention for constructing the hash structure.
Failed to use (a prefix of) the values generated by the hash function to index into the
bucket address table.
Failed to show the general case in Part (e).
CS5481 Data Engineering
1. 16%
The proof can be started with the following.
For a B+-tree with parameter n,
• a leaf node has between (n–1)/2 and n–1 search-key values
• an internal node has between n/2 and n children
• the root node has at least 2 children
Assignment 1
For a B+ tree with parameter n and tree height h, the number of search-key values K falls in
2(�𝑛𝑛�)h−2 ��𝑛𝑛 − 1�� ≤ 𝐾𝐾 ≤ (𝑛𝑛 − 1)𝑛𝑛h−1 22
To complete the proof, you need to derive both the lower bound and the upper bound for h. In the case of upper bound, you may need to consider two cases in which the parameter n is odd or even.
the following range:
CS5481 Data Engineering Assignment 1 2. 42%
(a) A taller B+-tree with the same value of n using the same set of search-key values in the leaf nodes of the given tree.
(b)
Insert 30
77
85
51
53
80
88
41
41
51
53
77
80
85
88
23
36
Insert 83
Insert 10
CS5481 Data Engineering Assignment 1
(c) A tree with 2 levels after deleting 88, 85, 83, 53, 30 and 36.
41
53
77
80
41
51
10
23
CS5481 Data Engineering Assignment 1
3. 42%
(a) 48
(b) 4
(c) The hash structure after inserting 14, 15, 31, 47
4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1
: :
2
: :
3
4
14
4
15
31
47
CS5481 Data Engineering Assignment 1
(d) 7, the hash structure after inserting 0, 8, 12, 14, 15, 31, 47
(e) m + n
4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1
0
: :
2
8
: :
3
12
4
14
4
15
31
47