A binary search tree that keeps every old version. An update copies only the path from the root to the change; everything else is shared between versions.
This interactive visualization needs JavaScript.