Immutable does not mean you have to copy the whole structure. You can store only the changes. This is how immutable data structures work in functional languages such as Haskell.
I know about different data structures but they are all more complicated than mutable data structures. For example, if you "store only changes", it will take more time to access the data, and you need to flatten your changes once in a while.
Also, for nested data structures you need to either do path copying, or use "modification boxes" [1].
Also, for nested data structures you need to either do path copying, or use "modification boxes" [1].
[1] https://en.wikipedia.org/wiki/Persistent_data_structure#Tech...