B+ Tree Design Requirements

As shown in the roadmap, you will now be required to support deletion of keys (loci) from the data dictionary. Thus, one change from Part 2 to Part 3 is that the remove operation of the SortedMap interface should no longer throw the UnsupportedOperationException. However, you are not required to implement remove for entrySet, keySet, or values because remove will remain an optional operation, with an extra credit point value, for those of you who choose to do it.

There is one major change to the B+ tree definition in the Part 3 specification:

Part 2:

A leaf must always contain between ceiling($(order-1)/2$) and $order-1$ (non-null) keys, inclusive.

Part 3:

A leaf must always contain between ceiling($(order)/2$) and $order$ (non-null) keys, inclusive.

This will let us give those of you with no Part 2 credit for a working B+ tree a few points for understanding someone else's code well enough to modify it. It will also demonstrate the benefit of object oriented design in dealing with unexpected changes in the specification. You may refer back to the section 7.2 (in the Part 2 portion) of this specification should you have any other questions regarding the B+ tree implementation.