Exercises on B Trees

1. Insert the values 18, 5, 14, 19, 8, 10, 11 into the given B-tree of order 4 (i.e. a 2-3-4 tree).

 --------------------
 | 12 | 16 |
 --------------------
  / | \
 / | \
 ------------- ------------ --------
 | 7 | 9 | | 13 | 15 | | 20 |
 ------------- ------------ --------
 

Try the insertions using splitting on the way down, and then try again propagating splits upwards.

2. Given the following B-tree of order 7, delete the key 25.

 -------------------------------------
 | 10 | 40 | 80 |
 -------------------------------------
 / | \ \
 / | \ \
 ------------------- ---------------- ---------------- ---------------------
 | 2 | 3 | 4 | 6 | | 20 | 25 | 30 | | 50 | 60 | 70 | | 82 | 84 | 86 | 88 |
 ------------------- ---------------- ---------------- ---------------------
 

3. What is the maximum number of keys that can be stored in a B-tree of order 200 with 4 levels (including the root)?
4. Assuming that the retrieval of each node of a B-tree of order 200 requires 2 disk accesses (regardless of how many keys are stored at the node), what is the maximum number of disk accesses required to retrieve a key, if the B-tree contains 5 million keys? (Hint: Compute the maximum number of levels that might be required to store 5 million keys in a B-tree of order 200).
5. Reconsider the previous question, assuming that the B-tree is of order 100, and each node only requires one disk access. Which tree requires fewer disk accesses in the worst case?