Table of Contents

Compound Move/MoveValue (field-update fast path)

Atomic remove+insert for indexed-field updates — one traversal, one lock on the common same-leaf case.

Status: ✅ Implemented · Visibility: Internal · Category: Indexing

🎯 What it solves

Updating an indexed field's value (a position changing, a status enum flipping) requires the index to relocate the entity from its old key to its new key. A naive implementation does this as two independent operations — remove the old key, insert the new key — each paying its own lock acquisition and full root-to-leaf traversal. For AllowMultiple indexes the naive path is worse still: each half also has to resolve its own HEAD buffer before it can splice the entity out of one key's set and into the other's. Most field updates are small (a counter increment, a position nudge), so the old and new keys frequently land in the same leaf — making the second traversal pure waste.

⚙️ How it works (in brief)

Move (unique indexes) and MoveValue (AllowMultiple indexes) descend for both the old and new key in one pass, sharing the common root-to-fork path. If both keys resolve to the same leaf, the operation takes a single write-lock and performs the remove and insert as one in-node operation — no entry-count change, so no split/merge risk. If the keys resolve to different leaves, both are locked in ascending chunk-id order (deadlock-free) and the remove/insert happen under that paired lock; if either leaf can't safely absorb the change in place, the call falls back to a pessimistic, structurally-aware path. For MoveValue, the HEAD buffer IDs for both the old and new key are read inline while the leaf is already locked, instead of issuing separate lookups afterward. This is entirely internal — there is no separate API to invoke; any commit that changes an indexed field's value uses this path automatically.

💻 Usage

[Component("Game.Unit", 1, StorageMode = StorageMode.SingleVersion)]
struct Unit
{
    [Index]                         // unique index → uses compound Move
    public int Id;

    [Index(AllowMultiple = true)]   // secondary, multi-value → uses compound MoveValue
    public int Status;
}

[Archetype]
partial class UnitArchetype : Archetype<UnitArchetype>
{
    public static readonly Comp<Unit> U = Register<Unit>();
}

using var tx = dbe.CreateQuickTransaction();
EntityRefMut e = tx.OpenMut(id);
Unit u = e.Read(UnitArchetype.U);
u.Status = (int)UnitStatus.Engaged;
e.Set(UnitArchetype.U, u);   // indexed field change
tx.Commit();                          // index relocation runs as a single compound Move/MoveValue — no app code involved

There is no tuning knob — the engine always attempts the same-leaf fast path first, falls back to the dual-leaf path, and finally to the pessimistic path; the choice is made per-call based on where the old and new keys land.

⚠️ Guarantees & limits

  • Triggered automatically whenever a transaction commits a change to a field carrying [Index] — no separate API call exists, and there is nothing to opt into or out of.
  • Same-leaf updates take exactly one write-lock and one traversal; cross-leaf updates take two write-locks, acquired in ascending chunk-id order to avoid deadlocks, after a single shared traversal prefix.
  • The old key's entry is only removed once the new key is confirmed absent (unique indexes) or the buffer operations succeed (multi-value indexes) — a failed move leaves the index unchanged, not half-applied.
  • If a cross-leaf move would overflow the destination leaf or underflow the source leaf, it bails out of the optimistic path and falls back to a pessimistic, structurally-aware move (handles split/merge correctly); this fallback is rare in practice.
  • For AllowMultiple indexes, both HEAD buffers are resolved and spliced under the leaf write-lock the descent already holds — the buffer work issues no lookup of its own.
  • Design-time estimate: ~57-62% faster than Remove+Add for same-leaf moves, ~30-41% faster cross-leaf, and ~64-71% faster than the four-operation multi-value path; actual savings depend on how often field updates keep the entity in the same leaf.

🧪 Tests

  • OlcBTreeTests — the Compound Move/MoveValue section: same-leaf/cross-leaf Move, deadlock-free opposite-direction moves, MoveValue same-leaf/cross-leaf/last-element-removes-key, and the old-key-not-found/new-key-exists failure paths
  • ClusterIndexTests — TickFence_FieldMutation_BTreeMoveExecuted: end-to-end exercise of the same Move operation via the cluster/SV tick-fence deferred commit path

🔗 Related

Edit this page