CSE 241: More B-tree Practice Exercises
  1. What are the maximum number of keys that can be stored in a B-tree of height two (the root plus two additional levels) with a minimum branching factor of t=500?
    Solution
  2. For the following B-tree where t=3 show the result when "B" and then "Q" are inserted.
    Solution
  3. Consider the following B-tree where t=2. Show the B-tree that results when deleting "W". NOTE: The solution just shows the final answer. If you did not get that answer, come see us for help figuring out where you made a mistake. In your homework solutions you are expected to show the intermediate trees so that we can see your work.
    Solution

Solution to #1)

To maximize the number of keys stored in a B-tree with t=500, each node will have 999 keys and 1000 children. Thus the number of nodes in such a B-tree of height two will be 1+1000+ 1000^2 = 1,001,001. Thus the number of keys is 999 x 1,001,001 = 999,999,999