Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Persistent ordered indexes: copy search paths, share subtrees

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A persistent ordered index returns a new root for each edit while old roots remain valid. This immutable treap stores a search key, owner, random priority, and child references in each node. Split and merge rebuild only nodes on traversed paths; untouched subtrees are reused by identity. A new version can delete a key without deleting it from an earlier version. The binary-search ordering supports lookup and ordered traversal; the priority ordering gives expected balanced height when priorities are independent random values. Randomization is an expected-cost assumption, not a worst-case height guarantee.

Operational case

Version one contains asset 47 owned by North. Version two adds asset 61 owned by East. Version three removes 47, so its ordered output contains only 61; version one still contains 47. A fourth version branches from version two by adding 83, and its untouched left subtree is the identical node used by version two. A caller can hold any root as a point-in-time view. Node immutability makes sharing safe. A mutable owner object stored inside a frozen node would still let old versions appear to change, so the shown owners are immutable strings.

Working Python program

python
"""Immutable randomized treap with version roots and structural sharing."""

from dataclasses import dataclass
from random import Random


@dataclass(frozen=True)
class IndexNode:
    asset_id: int
    owner: str
    priority: int
    left: "IndexNode | None" = None
    right: "IndexNode | None" = None


def find(root, asset_id):
    while root is not None:
        if asset_id == root.asset_id:
            return root.owner
        root = root.left if asset_id < root.asset_id else root.right
    return None


def split(root, asset_id):
    """Return keys below asset_id and keys at or above it."""
    if root is None:
        return None, None
    if root.asset_id < asset_id:
        left_of_cut, right_of_cut = split(root.right, asset_id)
        return IndexNode(root.asset_id, root.owner, root.priority, root.left, left_of_cut), right_of_cut
    left_of_cut, right_of_cut = split(root.left, asset_id)
    return left_of_cut, IndexNode(root.asset_id, root.owner, root.priority, right_of_cut, root.right)


def merge(lower, upper):
    if lower is None:
        return upper
    if upper is None:
        return lower
    if lower.priority < upper.priority:
        return IndexNode(lower.asset_id, lower.owner, lower.priority, lower.left, merge(lower.right, upper))
    return IndexNode(upper.asset_id, upper.owner, upper.priority, merge(lower, upper.left), upper.right)


def put(root, asset_id, owner, priority):
    if find(root, asset_id) is not None:
        raise ValueError("duplicate asset")
    lower, upper = split(root, asset_id)
    return merge(merge(lower, IndexNode(asset_id, owner, priority)), upper)


def remove(root, asset_id):
    if root is None:
        raise KeyError(asset_id)
    if asset_id == root.asset_id:
        return merge(root.left, root.right)
    if asset_id < root.asset_id:
        return IndexNode(root.asset_id, root.owner, root.priority, remove(root.left, asset_id), root.right)
    return IndexNode(root.asset_id, root.owner, root.priority, root.left, remove(root.right, asset_id))


def ordered(root):
    if root is None:
        return []
    return ordered(root.left) + [(root.asset_id, root.owner)] + ordered(root.right)


priority_source = Random(4726)
version_zero = None
version_one = put(version_zero, 47, "North", priority_source.getrandbits(63))
version_two = put(version_one, 61, "East", priority_source.getrandbits(63))
version_three = remove(version_two, 47)
version_four = put(version_two, 83, "West", priority_source.getrandbits(63))
print(ordered(version_one))
print(ordered(version_three))
print(version_four.left is version_two.left)

Output

Output
[(47, 'North')]
[(61, 'East')]
True

Time, space, and tradeoff

Find takes expected O(log N) time for N keys. Split, merge, insertion, and deletion copy O(log N) nodes in expectation and take expected O(log N) time; an unlucky priority order can make any of them O(N). Across K versions, total retained memory is the initial tree plus nodes copied by edits, not a full O(N) map copy per version. The shown ordered traversal builds a list with O(N) time and O(N) output space; Python recursion also uses height-proportional stack space. Production systems need a rule for priority generation, recursion limits, version retention, and garbage collection. This structure is in memory, not a disk index.

Common Mistakes

  • Do not mutate an old node while creating a new version.
  • Do not promise worst-case logarithmic time for random-priority balancing.
  • Do not mistake a frozen node for deep immutability of objects referenced by its fields.
  • Do not retain every historical root forever without a storage budget.

Connected lessons

Test this contract in the live depot audit project, then check the operations quiz.

Implicit treap: edit positions and reverse a range extends this operation contract.

Bitmap hash tries: copy paths for immutable alert maps adds a keyed lookup comparison.

Ordered treaps: split, join, and select depot keys adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details