fractional-keys

A dependency-free TypeScript implementation of fractional indexing: lexicographically-sortable order keys for inserting, moving, and reordering items in a list without renumbering neighbors. Used for z-order and list ordering in Figma, Linear, Excalidraw, and similar collaborative tools.

Why this one

Pick fractional-keys if you want:

• Branded FractionalIndex type for nominal safety at API boundaries.
• Collision-resistant jittered variants for concurrent inserts.
• Custom alphabets, including a working BASE_95_DIGITS with correctness fixes for non-'0' zero digits.
• sideEffects: false, tree-shakeable, no runtime dependencies. Node ≥ 18.

Install

npm install fractional-keys

Usage

import { generateKeyBetween, generateNKeysBetween } from 'fractional-keys';

generateKeyBetween(null, null);   // "a0"   (first element)
generateKeyBetween("a0", null);   // "a1"   (append)
generateKeyBetween(null, "a0");   // "Zz"   (prepend)
generateKeyBetween("a0", "a1");   // "a0V"  (insert between)

generateNKeysBetween("a0", "a1", 10);
// ["a04", "a08", "a0G", "a0K", "a0O", "a0V", "a0Z", "a0d", "a0l", "a0t"]

Pass null or undefined for either bound to mean "past the start" or "past the end" of the list.

API

generateKeyBetween(a, b, digits?): FractionalIndex

Single key strictly between a and b. Throws FractionalIndexError if a >= b or if either input is not a valid key.

generateNKeysBetween(a, b, n, digits?): FractionalIndex[]

n keys in sorted order between a and b. Recursive splitting keeps length growth logarithmic in n.

Jittered variants

generateKeyBetween is deterministic, so two clients inserting at the same position compute the same key. To avoid ties without a separate tie-breaker column, use:

import {
  generateJitteredKeyBetween,
  generateNJitteredKeysBetween,
} from 'fractional-keys';

generateJitteredKeyBetween("a0", "a1");
// random key between "a0" and "a1", drawn from ~2^30 possibilities

Both accept an options object: digits, jitterBits (default 30), getRandomBit (default Math.random() < 0.5; pass a crypto.getRandomValues-backed function for cryptographic randomness).

With 30 bits of jitter, 100 concurrent inserts at the same position collide with probability ~0.0005%; 10 000 inserts, ~4.5%.

Validation

• validateOrderKey(key, digits?) throws if key is not a valid order key for the given alphabet.
• validateDigits(digits) throws if the alphabet has fewer than two characters, has duplicates, or isn't strictly ascending. Run it once at startup if you use a custom alphabet.

Constants

BASE_10_DIGITS, BASE_62_DIGITS (default, URL-safe), BASE_95_DIGITS (densest, not URL-safe).

Types

export type FractionalIndex = string & { readonly [FractionalIndexBrand]: true };
export class FractionalIndexError extends Error {}

FractionalIndex is a branded string. Functions return it; they accept plain string | null | undefined as input. Assert at the boundary if you want nominal typing in your own code.

Notes

Concurrency. Sort by (orderKey, clientId) or (orderKey, createdAt), or use jittered keys.

Storage. Use binary collation (COLLATE "C" in Postgres, utf8mb4_bin in MySQL) so locale-aware collations don't reorder characters. VARCHAR(64) is usually enough; regularly hitting the limit means it's time to rebalance.

Degradation. Repeated inserts into the same slot grow key length by ~1 character per insert. Periodically rebalance with generateNKeysBetween.

Credits

The base-62 algorithm, integer+fraction encoding, and recursive midpoint routine come from David Greenspan's Observable notebook (CC0). The jitter variants follow nathanhleung/jittered-fractional-indexing.

Further reading: Figma — Realtime editing of ordered sequences, rocicorp/fractional-indexing.

License

MIT