Persistent data structure: Difference between revisions

Revision as of 06:14, 20 March 2025

Revision as of 13:25, 20 June 2025

Line 27:

=== 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 <math>O(n·\cdot m)</math> performance characteristics for ''m'' modifications of an array of size ''n''.{{citation needed|date=May 2019}}

[[Copy-on-write]] memory management can reduce the price for an update from <math>\Theta(n)</math> to <math>O(Bu)</math>, where ''B'' is the memory block size and ''u'' the number of pages updated in an operation.{{citation needed|date=May 2019}}

===Fat node===