# 数据结构代写 | 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