Fractional Indexing Algorithm

ArticleAlgorithmsData StructuresOriginally published: January 2, 2025•Last updated: April 1, 2026

Library: frac-indexes

Full documentation, API reference, and quick start live on the project documentation site.

Source code is on GitHub. Install from npm: npm install frac-indexes

Fractional indexing is a way to give every row in an ordered list a key that still sorts correctly after you insert, move, or batch-update items—without rewriting the whole list. It shines when several people or devices touch the same ordering at once.

What problem does it solve?

Traditional approaches like integer positions (0, 1, 2, …) break down as soon as you insert between two items: you either renumber everything or run out of gaps. Fractional indexing stores a numeric key per item (often a decimal). New keys are chosen strictly between neighboring keys, so order is preserved and the database or sync layer only updates the rows that moved.Typical use cases:

Collaborative lists — Kanban columns, playlists, doc outlines, task priorities.
Offline-first / CRDT-style UIs — generate a new key locally without a central “next index” counter.
Flexible placement — insert at the start, between two items, or at the end with the same API shape.

What you usually need from the API

A practical library or module tends to expose:

Flexible insertion — Place one item before the first, between two neighbors, or after the last.
Bulk insertion — Add many items in one pass to cut round-trips when importing or duplicating blocks.
Relocation — Move one or many items to a new position (new keys between the target neighbors).

Those three cover most product flows without forcing a global reorder job.

Core idea: `generateFractionalIndex`

The heart of the system is a function that takes the previous and next index (either may be missing at the edges) and returns a new value between them.Conceptually:

Measure the gap between prev and next when both exist. A common pattern is to step a fraction of that gap (for example one third of the span) so you leave room for future inserts on either side.
Apply a fixed minimum step (e.g. 0.001) so tiny gaps still produce distinct values after rounding.
Add jitter — a small random component (e.g. derived from a five-digit random value) so concurrent clients rarely pick the exact same float.
Round to a fixed number of decimal places (e.g. five) so storage and JSON stay stable and comparisons stay predictable.

Edge cases are handled explicitly: inserting at the head (no prev), at the tail (no next), or into an empty list (neither neighbor).

Reference implementation (TypeScript-style)

The following mirrors the behavior described in the slide deck: bounded step, jitter, and fixed precision.

const DECIMALS = 5
const MIN_STEP = 0.001
 
/** Map 0..99999 → tiny positive jitter (deck: five-digit random component). */
function jitter(): number {
  return Math.floor(Math.random() * 100_000) / 1_000_000_000
}
 
function round5(n: number): number {
  const f = 10 ** DECIMALS
  return Math.round(n * f) / f
}
 
/**
 * Returns a new fractional index between prev and next (exclusive bounds when both set).
 */
export function generateFractionalIndex(prev: number | null, next: number | null): number {
  const j = jitter()
 
  if (prev == null && next == null) {
    return round5(0.5 + j)
  }
  if (prev == null) {
    return round5(next! - MIN_STEP + j)
  }
  if (next == null) {
    return round5(prev + MIN_STEP + j)
  }
 
  const span = next - prev
  const step = Math.max(span / 3, MIN_STEP)
  const candidate = prev + step + j
  // Stay strictly inside (prev, next) if jitter overshoots
  const capped = Math.min(candidate, next - MIN_STEP / 2)
  return round5(Math.max(capped, prev + MIN_STEP / 2))
}

Store these numbers in the database as REAL/DOUBLE or as a fixed-precision string; sort by the numeric value for display order.

Collision probability and step size

Tighter minimum steps and higher decimal precision give more distinct slots before two clients collide. The deck summarizes how step size trades off against the effective key space (illustrative orders of magnitude):

Step size	Order of magnitude for “slots” in a unit interval	Collision risk (intuition)
`0.01`	~10² distinct steps per order of magnitude	Higher
`0.001`	~10³	Lower
`0.0001`	~10⁴	Lower still

Jitter pushes concurrent collisions from “same float” to “astronomically unlikely” for typical apps; if you need stronger guarantees, pair fractional keys with a tie-breaker (timestamp, client id, or lexicographic suffix).

Packaging and integration

A small fractional-indexing module can wrap:

Key generation (single and bulk),
Validation that keys stay ordered,
Helpers for “move block from index A to between B and C”.

That keeps your UI and sync layer thin: columns only store id, position_key, and maybe updated_at.

Open source: `frac-indexes`

The reference implementation and packaging from the same project line live here:

GitHub: github.com/SylonZero/frac-indexes
npm: npm install frac-indexes

Contributions and issue reports are welcome if you extend the API or harden edge cases for your stack.

Takeaways

Fractional indexing avoids global renumbering by always allocating keys between neighbors.
Jitter + fixed decimal rounding keep concurrent inserts from colliding in practice.
Head, middle, and tail insertion share one mental model—pass null for the missing neighbor.
For production, combine with bulk and move helpers, and tune step size / precision to your expected list depth and concurrency.

“The only source of knowledge is experience.”
— Albert Einstein