5.6.3 2-3 Trees and B-Trees

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 + dlog₂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?