- 1.
- For a 2-3 tree with
*n*leaves, compute the following:- (a)
- Minimum height
- (b)
- Maximum height

- 2.
- For a 2-3 tree with height
*h*, compute the following:- (a)
- Minimum number of leaves
- (b)
- Maximum number of leaves

- 3.
- What are the minimum and maximum numbers of internal nodes a B-tree
of order
*m*and height*h*(ie. (*h*+ 1) levels) may have? - 4.
- Suppose we insert the keys 1,2, ..., in ascending order into an initially empty 2-3 tree. Which key would cause the leaves to be at level 4 for the first time? (Assume that the root is at level 1). Write down the resulting 2-3 tree.
- 5.
- Devise an algorithm to find the
*k*^{th}largest element in a- (a)
- 2-3 tree.
- (b)
- B-tree.

- 6.
- Suppose that the keys
1, 2,..., 20, are inserted in that order into
a B-tree with
*m*= 2. How many internal nodes does the final B-tree have? Show the final B-tree. Compare this with a binary search tree for the same sequence of inserted elements. Assume that each leaf block can only store one record. - 7.
- Suppose that the keys
1, 2,..., 20, are inserted in that order into
a B-tree with
*m*= 4. How many internal nodes does the final B-tree have? Show the final B-tree. Compare this with a 4-way search tree for the same sequence of inserted elements. Assume that each leaf block can only store one record. - 8.
- Given a B-tree, explain how to find
- (a)
- the minimum key inserted.
- (b)
- predecessor of a given key stored.
- (c)
- successor of a given key stored.

- 9.
- Suppose we have a file of one million records where each record takes 100 bytes. Blocks are 1000 bytes long and a pointer to a block takes 4 bytes. Also each key value needs two bytes. Devise a B-tree organization for this file.
- 10.
- Design a B-tree organization if it is required to contain at least one billion keys but is constrained to have a height of 4 (ie. 5 levels). Assume that the number of records for each leaf block is 16.
- 11.
- Compute the smallest number of keys, which when inserted in an
appropriate order will force a B-tree of order 5 to have exactly
*m*levels (root at level 1 and leaves at level*m*). - 12.
- A
*B*^{*}-tree is a B-tree in which each interior node is at least 2/3full (rather than half full). How do the algorithms for search and delete change for a*B*^{*}-tree? What would be the advantages and disadvantages of*B*^{*}-trees compared to B-trees? - 13.
- Assume that it takes
*a*+*bm*milliseconds to read a block containing a node of an m-ary search tree. Assume that it takes*c*+*d*log_{2}*m*milliseconds to process each node in internal memory. If there are*n*nodes in the tree, compute the total time taken to find a given record in the tree. - 14.
- Suppose that disk hardware allows us to choose the size of a disk
block arbitrarily, but that the time it takes to read the disk block
is
*a*+*bt*, where*a*and*b*are specified constants and*t*is the degree of a B-tree that uses blocks of the selected size (i.e. each disk block contains (*t*- 1) key values and*t*pointers). Assume that a total of*N*records are stored in the B-tree database, with each disk block storing one record.- (a)
- Compute the minimum number of disk blocks required by the above B-tree organization, including the blocks for storing the records.
- (b)
- Assuming that any record is equally likely to be searched for, estimate the total average disk block reading time for accessing a record.
- (c)
- How do you choose
*t*so as to minimize the total average disk block reading time?