The Fat Node Method

Another persistence technique: store all versions of each field in the node itself.

class FatNode:
    versions: list of (timestamp, value)
    leftVersions: list of (timestamp, Node)
    rightVersions: list of (timestamp, Node)

    function getValue(time)
        // Binary search for latest version <= time
        return latest entry in versions with timestamp <= time

Pros:

• Simpler for some structures
• No tree shape required

Cons:

• Access time includes binary search: $O(\log m)$ where $m$ is modifications to that node
• Can be $O(\log n \cdot \log m)$ total

Path copying is usually preferred for trees. Fat nodes work well for simpler structures.