FAQ for Assignment 3
For problem 1, what do you mean by "the keys are not redistributed"? Don't keys have
to be redistributed after a block is split or coalesced?
There are two ways that have been suggested to handle a B+-tree block that overflows. One approach is to split the
overflowed block, and move half the keys into the new block. A second approach is to redistribute keys among
existing blocks. By "keys are not redistributed" we mean that you should use the first approach (split blocks) and
not the second (redistribute among existing blocks). Similarly, when a block is underfull, there are two things
that could be done: coalesce the underfull block with another block, or redistribute the keys while keeping the
number of blocks the same. By "keys are not redistributed" we mean that you should use the first approach
(coalesce blocks) not the second (redistribute among existing blocks).