Fractional index ordering

Definition

This is an approach you use when you change item order frequently in a list or tree, and want the order not to break even when several people edit at the same time. Instead of an integer number (0,1,2…) per item, you attach a sortable string key and insert relative to a neighbor, like "put this after B."

More precisely, fractional indexing is an ordering model that gives each collection item a string key comparable by lexicographic sort (comparing strings in dictionary order) (called the position), and expresses insert·move intent not as "index n" but as a neighbor anchor id (after/before — the reference point indicating which item to place before/after). On a middle insert, it doesn't change existing items' keys; it only generates a new key between two keys.

Why it's needed

Ordering with an integer index causes these problems. (1) Every time you insert one in the middle, you must renumber all following items, (2) if two people simultaneously "insert at the same slot 3," they collide, and (3) a late edit anchored on an already-deleted item (a stale patch — an outdated, no-longer-valid change request) fails.

For data where order changes are frequent and multiple clients touch it concurrently — a collaborative todo list·document block sibling order·kanban cards — practitioners often choose fractional keys + "neighbor-relative" intent + tie-break (a rule for resolving ties) over integers to avoid these three problems.

How it works

1. Storage layer: position: string per sibling (e.g. "a0", "a0V").
2. Intent layer: patch { after: "block-a", block: newBlock }.
3. Sort: compare(position) lexicographic; on ties, (clientId, opId) tie-break.
4. Insert: generateKeyBetween(prev, next) — generate a string between two keys.
5. Rebalance: when a key grows long, reassign shorter keys while keeping the same order.

Practical application

When you promote/move a subtree to a different parent, reusing the nested position as-is can break the sort in the new sibling set — you need to reassign a position between the new bounds. In an offline replay, if the anchor was deleted, find a replacement anchor via a fallbackAfter[] chain or tail-append.

Trade-offs

• Key string length grows over time → periodic rebalance needed.
• Human-readable order numbers aren't stored — derive the UI ordinal at render time.
• Lighter than a full CRDT but requires a server/client merge policy·tie-break contract.

When not to use

• A small config array where order rarely changes and there's a single writer — an integer index is enough.
• Allowing offline with only a position key and no anchor fallback — stale-patch failure rate spikes.

Common mistakes

• Mixing index in the patch and position in storage — a mismatch between intent and SoT.
• sort-on-read everywhere — performance·consistency problems.
• Reusing position on promote — sibling sort corruption.
• Only position with no tie-break — concurrent insert is nondeterministic.

Related concepts

• optimistic-outbox-rebase — convergence of concurrent patches
• inverted-index-full-text-search — beware of confusion with a different kind of "index" (search)