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.
Pick fractional-keys if you want:
- Branded
FractionalIndextype for nominal safety at API boundaries. - Collision-resistant jittered variants for concurrent inserts.
- Custom alphabets, including a working
BASE_95_DIGITSwith correctness fixes for non-'0'zero digits. sideEffects: false, tree-shakeable, no runtime dependencies. Node ≥ 18.
npm install fractional-keysimport { 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.
Single key strictly between a and b. Throws FractionalIndexError if a >= b or if either input is not a valid key.
n keys in sorted order between a and b. Recursive splitting keeps length growth logarithmic in n.
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 possibilitiesBoth 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%.
validateOrderKey(key, digits?)throws ifkeyis 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.
BASE_10_DIGITS, BASE_62_DIGITS (default, URL-safe), BASE_95_DIGITS (densest, not URL-safe).
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.
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.
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.
MIT