Provide a sketch of the resulting tree.

computer science


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.

Related Questions in computer science category