What is an inverted dependency index in a reactive graph system, and how does it avoid O(n) recomputation?

An inverted dependency index is a data structure mapping leaf nodes directly to their upward subscribers, avoiding O(n) recomputation by replacing global graph traversal with localized, targeted bubbling.

How the Inverted Index Works

Mapping Direction: Instead of tracing top-down from roots to leaves, it maps a leaf or source node directly to the specific higher-level derivations that depend on it.

Direct Subscriptions: Each data point stores an explicit list of its direct upward listeners or parent nodes.

Avoiding O(n) Recomputation

Targeted Triggering: When a value updates, the system skips global diffs or full-tree crawls.

Bubbling Updates: It immediately activates only the exact chain of dependent nodes tied to the changed leaf.
Complexity Shift: Recomputation scale changes from total graph size O(n) to the length of the specific active dependency path O(k) where (k << n).