B+Tree: Duplicate Keys

Approach #1: Append Record Id

• Add the tuple's unique record id as part of the key to ensure that all keys are unique.

• The DNMS can still use partial keys to find tuples.

Approach #2: Overflow Leaf Nodes

• Allow leaf nodes to spill into overflow nodes that contain the duplicate keys

• This is more complex to maintain and modify