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).