数据结构代写 | AST20105 – Individual Assignment

这个作业是完成数据结构中的B树
AST20105 – Individual Assignment

Task Description
The project carries 25% of the term mark and this is an individual project. You are
required to complete a self-directed research on B-Tree (B tree, NOT B minus Tree),
and B+ Tree. Through searching texts, and the Internet, you should be able to
complete the following tasks. Be reminded when you are looking for information on the
Internet, be careful of its authenticity as some of the information may be confusing.
This project will not be discussed in lecture. You should go searching for various kinds
of sources of information and to conclude your thoughts.
IMPORTANT!!!
This is an individual project. You are encouraged to discuss with your classmates but
plagiarism is strictly prohibited. If any suspected plagiarism case is caught, you will be
summoned to explain your work. Excuses including “working together” will not be
accepted. All parties involved will receive the same penalty.
Submission Details
Submit the project by December 11 (Friday) 17:00. Submit your work in pdf format to
Moodle. Your work must be clearly written. You could submit electronically via Moodle
dropbox if you complete your work electronically, i.e. using word-processing tools.
If you choose to handwrite your work, you must submit your work on December 11 by
17:00 to the general office. If you handwrite your work, scanning or screen capturing
your work IS NOT accepted and it cannot be sent to Moodle. 30% mark penalty will be
asserted if you do so.
Late Submission Penalty
Your work should be clearly stated with your name, programme, and student id. Late
submission will be penalized, a deduction of 15% per day, up to 3 days. For Moodle
submission, the latest submission date will be December 14 midnight, with 45% mark
deduction. If you choose to submit your work to the general office, the latest
submission will be December 14 noon with 45% mark deduction. Anything later than
that will not be entertained.
1
AST20105 – Individual Assignment
Task 1: (13 points)
You are required to do a detailed comparison of the data structures of B Tree (B tree,
NOT B minus Tree), and B+ Tree. B+ Tree is an extension of B Tree. You are required
to complete the following sub-tasks:
A. Explain the usefulness of this kind of data structure. Why use B-trees / B+ trees
over AVL trees? (2 points)
B. Explain the trees’ node size in general. (1 points)
C. Explain the term M and L. (2 points)
D. List the properties of these kinds of trees. (2 points)
E. Make comparisons between B-Tree and B+Tree. (2 points)
F. For each the following B-Tree with an order M = 5, state whether they are valid.
For each invalid structure, explain briefly. (4 points)
Task 2: (4 points)
State the B+ Tree structures, with M = 4, after insertion of the following data. Show
your steps.
2, 3, 5, 7, 11, 17, 19, 23, 29, 31
2
AST20105 – Individual Assignment
Task 3: (8 points)
Study the following B+ Tree and complete all tasks.
A. State the order of the above B+ Tree. (1 point)
B. State the time cost, in terms of number of disk access, of the above tree. Be
reminded you should not provide any Big-O notation. (1 point)
C. Draw the resulting tree when “1” is inserted. (1 point)
D. Draw the resulting tree when “33” is inserted. (2 points)
E. Draw the resulting tree when “17” is inserted. (1 point)
F. Draw the resulting tree when “81” is deleted. (2 points)
Task 4: (Challenging!) 8 points
Using a B-Tree, we want to store and process information concerning the student
records in the ABC College. We assume the following:
● we have 300,000,000 items
● each key is 8 bytes (ID number)
● a record is 256 bytes
● one disk block holds 8,192 bytes, and
● a pointer to each block is of size 4 bytes.
A. What are the values of M and L in this case ? (4 points)
B. What is the number of leaf nodes in the best and worst cases? (2 points)
C. What is the height of the B-Tree in the worst case? (2 points)
3