Provide a sketch of the resulting tree.
computer science
Description
Question 1
You are given the list of 12 integers
[8,91,2,7,3,5,18,19,22,34,54,77] to add to a Binary Search Tree in that
sequence.
i.
Provide a sketch of the resulting tree.
ii.
Is this an efficient structure to use to
search for values (that may or may not be in the original list)? Explain your answer clearly using
illustrations as needed.
Question 2
Insert the same sequence of integers
[8,91,2,7,3,5,18,19,22,34,54,77] into a B-tree with order 3.
i.
Provide a sketch of the resulting tree
structure.
ii.
If you add the same integers in a different
order, e.g. [18,8,54,77,2,91,7,3,22,34,5,19], will you get an identical
tree? Explain why this is the case. Use illustrations if needed.
iii.
Describe the step-by-step process of what
happens when 18 is removed from the B-tree created in part (i).
Question 3
iii.
B+trees are used extensively by MySQL: why
might a B+ tree be a better choice than a B-tree for storing a database table
index? For what kinds of query would a
B+tree index be expected to provide better performance than one using the
B-tree structure?
ii. Given the following:
·
hard disk block size is 16 kilobytes (assume
1 kilobyte = 1024 bytes)
·
a key (K) is 12 bytes
·
a tree pointer P is 6bytes
·
a data pointer (Pr) is 8 bytes
If building a B-tree or a B+tree index, how much larger
will the order of a B+tree (internal nodes) be than the order of a B-tree? Explain your answer.
