Fractional Indexing: Ordering Items in Collaborative Lists

The problem

Canvas editor, 500 layers, the user drags layer #200 onto position #450. If the order is stored as plain integers 1, 2, 3, ..., 500, moving a single element means renumbering every element after the insertion point.

Tolerable for a local app. In a collaborative setting it’s a nightmare:

• Every index update is a separate operation that can conflict with other users’ actions.
• Moving one layer means 250 index mutations, one per element between the old and new position.
• If two people drag different layers at the same moment, merging becomes a problem of reconstructing order rather than applying two patches.

What you want: O(1) insert, and existing elements stay untouched.

Why not float indexes

First idea that comes to mind: use floats instead of integers. Between 1 and 2 you can always insert 1.5, between 1 and 1.5 insert 1.25, and so on.

It works right up to the first degradation:

11.0, 2.0
2→ insert between: 1.5
3→ insert between 1.0 and 1.5: 1.25
4→ insert between 1.0 and 1.25: 1.125
5→ ...
6→ after ~50 inserts at the same point, float64 precision runs out

Past that point, (1.0 + 1.0000000000000002) / 2 === 1.0000000000000002, and the new element gets a key equal to its neighbor. Order breaks.

The fix: string keys that compare lexicographically and can grow in length without losing precision.

The idea

Between any two strings "a" and "c" there’s a string "b" that sits lexicographically in the middle. For "a" and "b", add a character: "aV" fits between them because "a" < "aV" < "b". For "a" and "aV", the answer is "aF". Length grows, but the key always exists.

1Elements: [A,   B,   C,   D,   E  ]
2Keys:     ["a0", "a1", "a2", "a3", "a4"]
3
4Insert X between B and C:
5→ generate a key between "a1" and "a2" → "a1V"
6→ result: ["a0", "a1", "a1V", "a2", "a3", "a4"]
7→ not a single existing key changed

That’s fractional indexing. A few solid implementations exist. The classic JS version is fractional-indexing by Rocicorp. I maintain my own dependency-free TypeScript package fractional-keys with jitter and arbitrary-alphabet support. Both follow the formal description in David Greenspan’s notebook (2020), where the algorithm is derived step by step with tests.

How midpoint works

A general model is enough to reason about behavior. For the full details, go to Greenspan’s notebook: step-by-step derivation with tests.

A key is a string of digits from a base62 alphabet (0-9A-Za-z, 62 characters), interpreted as a fraction. The function midpoint(a, b) returns a string strictly between a and b lexicographically, by four rules:

1. Common prefix is factored out: midpoint("a1", "a3") = "a" + midpoint("1", "3") = "a2".
2. A free digit between the first characters, take its median: midpoint("1", "5") → "3".
3. Adjacent neighbors, extend the string: midpoint("1", "2") → "1V" (V is the middle of the base62 alphabet).
4. Boundary cases (null as start or end) are handled separately via sentinel values.

Plus a ban on trailing zeros: "30" and "3" would look like different keys, but no key fits between them, so such strings are disallowed up front.

One more detail: the integer prefix (a0, b00, c000…). The leading letter encodes the length of the “integer” part of the key: a = 1 digit, b = 2 digits, c = 3, and so on. That’s why appending past "az" rolls to "b00" and not "a10": the prefix signals that the integer part grew by one, which keeps lexicographic string order lined up with numeric order even as keys get longer. End-user code rarely touches this, but it’s the reason the alphabet looks asymmetric at the boundaries.

The algorithm doesn’t care about the specific alphabet. base62 is a default. fractional-keys also supports base95 (all printable ASCII) for ~10% shorter keys under heavy middle-insertion, at the cost of characters that need escaping in JSON or URLs. Most projects stay on base62.

The API you work with

In practice one function carries the whole algorithm:

1import { generateNKeysBetween } from 'fractional-keys';
2
3// Generate N keys strictly between a and b.
4// Either end can be null — meaning a list boundary.
5generateNKeysBetween(
6  a: string | null | undefined,
7  b: string | null | undefined,
8  n: number,
9): FractionalIndex[]

That covers every operation. Two assumptions are implicit. First, every element carries a stable id separate from its index, so concurrent edits reference the same element across sessions. Second, rendering sorts the array by key on read (or maintains it sorted on every insert): fractional keys give you the order, not the storage layout.

Three edge cases are worth walking through.

Edge cases: batch inserts

1. Bulk insert at the tail

The most common scenario. The user adds 10 items at the end of the list.

1const last = elements[elements.length - 1]?.index ?? null; // "a4"
2const keys = generateNKeysBetween(last, null, 10);
3// → ["a5", "a6", "a7", "a8", "a9", "aA", "aB", "aC", "aD", "aE"]

Keys march through the alphabet, length stays stable. Best case, zero degradation.

2. Bulk insert at the head

The user imports 10 items that need to sit at the bottom of the z-order.

1const first = elements[0]?.index ?? null; // "a0"
2const keys = generateNKeysBetween(null, first, 10);
3// → ["Zq", "Zr", "Zs", "Zt", "Zu", "Zv", "Zw", "Zx", "Zy", "Zz"]

More interesting here. To be smaller than "a0", a key needs a first character smaller than 'a'. The algorithm uses uppercase A-Z as a “negative” prefix: in ASCII they sit before lowercase. Inside the Z prefix keys walk backwards through the alphabet: Zz, Zy, Zx, …, Z0. When those 62 slots are spent, the next prepend jumps to a longer prefix: Yzz, Yzy, … (3 characters), then Xzzz…, and so on. Slower than append, still no renumbering.

3. Bulk insert in the middle

The biggest source of degradation:

1const keys = generateNKeysBetween("a0", "a1", 10);
2// → ["a04", "a08", "a0G", "a0K", "a0O", "a0V", "a0Z", "a0d", "a0l", "a0t"]

The tighter the neighbors and the more keys you ask for, the longer the result. If the user keeps inserting at the same point (classic scenario: duplicating a layer with Cmd+D), lengths grow:

1Step 0: ["a0", "a1"]                       — 2 chars
2Step 1: ["a0", "a0V", "a1"]                — 3 chars
3Step 2: ["a0", "a0G", "a0V", "a1"]         — 3 chars
4Step 3: ["a0", "a08", "a0G", "a0V", "a1"]  — 3 chars
5...
6Step N: after ~25 inserts at the same point, length already passes 14 chars.

Keys don’t break, but they start eating memory, DB index space, and network bandwidth. The fix is periodic rebalancing (reindex) of the whole list back to clean integer-like values. When to trigger it depends on the app. In Figma and Linear the reindex is lazy, firing only when degradation is spotted.

Invalid state and repair

In a collaborative setting, array order and the actual keys can drift apart. Two clients merge changesets, and an element lands between two neighbors in the array while its index string falls outside their range.

Repair is two steps. First, find invalid segments: contiguous stretches of elements whose key fails prev < current < next. Then regenerate keys inside each segment via generateNKeysBetween from the nearest valid bounds.

The validity check reads like the definition:

 1const isValidFractionalIndex = (
 2  index: string | undefined,
 3  predecessor: string | undefined,
 4  successor: string | undefined,
 5) => {
 6  if (!index) return false;
 7  if (predecessor && successor) return predecessor < index && index < successor;
 8  if (!predecessor && successor) return index < successor; // first element
 9  if (predecessor && !successor) return predecessor < index; // last
10  return true; // only one
11};

Leave valid keys alone: a needless rewrite in a collaborative session cascades updates to every client.

Production pitfalls

Two things that both canonical sources (Greenspan and the Figma blog) skip.

Collation and column length

If keys live in Postgres or MySQL, the default collation isn’t binary. en_US.UTF-8 can decide that "a" < "B" or mix case in ways that don’t match JS lexicographic comparison. That breaks the whole algorithm: validation passes on the client, and ORDER BY on the server returns a different order.

Fix: store the column with COLLATE "C" (Postgres) or utf8mb4_bin (MySQL) for byte-level comparison. And pick a realistic VARCHAR(n): 32–64 characters cover any practical scenario with headroom; 255+ is a signal to reindex.

Client races

Two users insert an element between "a1" and "a2" at the same instant. Both locally call generateKeyBetween("a1", "a2") and both get "a1V", the same key. After sync, two elements share an order key, and their relative position is undefined.

Fractional indexing doesn’t solve this on its own. Two approaches work in practice. The first is a tiebreaker on a (orderKey, clientId) or (orderKey, createdAt) pair. Cheap, catches every tie. In CRDT systems like Yjs it’s built in; in a hand-rolled setup it gets added by hand at sort time. The second is jittered keys: instead of an exact midpoint, N bits of randomness are mixed in. In fractional-keys that’s generateJitteredKeyBetween(a, b, { jitterBits: 30 }). Two clients inserting between the same neighbors at the same moment get different keys with probability ~1 − 2⁻³⁰. The trade-off is longer keys.

Practical recipe: tiebreaking on the tuple [index, id] covers 99% of cases. Jitter makes sense when adding a second column to the DB index is more painful than carrying a longer key.

Moves and ghost elements

Insert and delete are atomic, but a “move” is delete at old position + insert at new position, two operations. If they cross the network at different times or one gets lost, the list ends up with a ghost (the old copy survived) or a disappeared element (the new one never made it). Canonical write-ups skip this case.

Fix: treat move as a single operation at the sync layer, not as two independent ops. Either the engine replays move(id, newIndex) atomically, or the delete carries a pointer to its paired insert so the reconciler can detect partial state. In CRDT land Automerge has a built-in A.move; in a hand-rolled protocol you add it yourself.

Reindexing without races

Rebalance is the standard cure for long keys, and in a collaborative setting it has its own race problem. If every client independently decides to reindex, they overwrite each other’s keys and broadcast N updates each. Merge turns the whole list into junk.

Rebalance is a single-writer operation. Options, in order of preference:

• A server-side job runs reindex under an exclusive lock and broadcasts the result as one atomic op.
• One client holds a “leader” role (lowest clientId, or elected on session start) and is the only one allowed to rebalance.
• Skip rebalance entirely and raise the column length: keys don’t degrade silently, and 128 chars usually covers the lifetime of a document.

When fractional indexing isn’t the right tool

• Access by position. “Give me the 200th element” is O(N) because the array is ordered by key, not by position. If that happens often, add another structure.
• Short-lived lists without collaboration. A plain array with integer indexes is simpler and faster.
• Hard limits on key length (databases with fixed-length string columns). Either aggressive reindexing or pick a different approach.
• Full CRDTs (Yjs, Automerge) already solve this and a dozen neighboring problems. If the project is already on them, a separate implementation is redundant.

Comparing approaches

Fractional indexing sits between integers and full CRDTs. More involved than integer indexes, way simpler and cheaper than a CRDT for the narrow “ordered list” job.

One note on the last row: Yjs (YArray) and Automerge (A.list) don’t use fractional indexing internally. They keep order with operation-based CRDTs: double-linked lists of ops plus Lamport-style IDs and tombstones for deletes. Same end result, different data structure. That’s why they carry more memory per element and why moves can be primitive operations instead of delete+insert pairs.

Where it’s used

• Figma, z-order of canvas layers (blog post).
• Linear, task order across lists and projects.
• Excalidraw, z-order of diagram elements (source).
• Notion, Craft, block order inside documents.

References

Implementations:

• fractional-indexing: JavaScript implementation by Rocicorp, the best-known package.
• fractional-keys (source): my dependency-free TypeScript package with branded types, custom alphabets (including base-95), a jittered variant for collaborative scenarios, and 173 tests.
• Excalidraw fractionalIndex.ts: production example with validation and batch regeneration.

Primary sources:

• Figma: Realtime editing of ordered sequences: 2017, popularized the technique for a collaborative editor.
• Implementing Fractional Indexing: 2020, Greenspan’s formal algorithm (CC0).
• AutoSplitKey — Microsoft Dynamics NAV: the ERP predecessor with numeric gaps.