Content deleted Content added
m Added information on partially persistent data structure |
Tag: Reverted |
||
Line 28:
=== Copy-on-write ===
One method for creating a persistent data structure is to use a platform provided ephemeral data structure such as an [[Mutable array|array]] to store the data in the data structure and copy the entirety of that data structure using [[Copy-on-write|copy-on-write semantics]] for any updates to the data structure. This is an inefficient technique because the entire backing data structure must be copied for each write, leading to worst case O(n·m) performance characteristics for m modifications of an array of size n.{{citation needed|date=May 2019}}
====Complexity of copy-on-write node====
Copy-on-write structures aim to minimize the time complexity of modifications by avoiding unnecessary copying of data. When a modification is made, the structure creates a new copy of the affected nodes only if they are shared with other versions. Otherwise, it modifies the existing node directly. Therefore, the modification time complexity depends on the cost of updating the affected nodes and potentially copying them if necessary. In many cases, this results in an amortized constant-time complexity for modifications. The space complexity for modifications in copy-on-write structures depends on whether a copy is made during the modification process. If a copy is required, the space complexity would be O(n), where n is the size of the affected portion of the data structure. However, if no copy is made (i.e., the modification is performed in place), the space complexity would be O(1) additional space.
===Fat node===
| |||