Fractional Indexing

This is based on Implementing Fractional Indexing by David Greenspan .

Fractional indexing is a technique to create an ordering that can be used for Realtime Editing of Ordered Sequences.

This implementation includes variable-length integers, and the prepend/append optimization described in David's article.

API

generateKeyBetween

Generate a single key in between two points.

generateKeyBetween(
  a: string | null | undefined, // start
  b: string | null | undefined, // end
  digits?: string | undefined = BASE_62_DIGITS, // optional character encoding
): string;

import { generateKeyBetween } from 'fractional-indexing';

const first = generateKeyBetween(null, null); // "a0"

// Insert after 1st
const second = generateKeyBetween(first, null); // "a1"

// Insert after 2nd
const third = generateKeyBetween(second, null); // "a2"

// Insert before 1st
const zeroth = generateKeyBetween(null, first); // "Zz"

// Insert in between 2nd and 3rd (midpoint)
const secondAndHalf = generateKeyBetween(second, third); // "a1V"

generateNKeysBetween

Use this when generating multiple keys at some known position, as it spaces out indexes more evenly and leads to shorter keys.

generateNKeysBetween(
  a: string | null | undefined, // start
  b: string | null | undefined, // end
  n: number // number of keys to generate evenly between start and end
  digits?: string | undefined = BASE_62_DIGITS, // optional character encoding
): string[];

import { generateNKeysBetween } from 'fractional-indexing';

const first = generateNKeysBetween(null, null, 2); // ['a0', 'a1']

// Insert two keys after 2nd
generateNKeysBetween(first[1], null, 2); // ['a2', 'a3']

// Insert two keys before 1st
generateNKeysBetween(null, first[0], 2); // ['Zy', 'Zz']

// Insert two keys in between 1st and 2nd (midpoints)
generateNKeysBetween(second, third, 2); // ['a0G', 'a0V']

Sorting

The indexes generated by this library are case-sensitive. While Array.prototype.sort will work out of the box, note that String.prototype.localCompare works case-insensitively and will give an incorrect ordering if used as a sort predicate. Instead, use native string comparison:

const arr = [
  {
    id: "todo_1253241",
    content: "Read the docs",
    fractionalIndex: "YzZ"
  },
  {
    id: "todo_8973942",
    content: "Open a PR",
    fractionalIndex: "Yza" 
  }
]
const sorted = arr.toSorted((a, b) =>
  a.fractionalIndex < b.fractionalIndex
    ? -1
    : a.fractionalIndex > b.fractionalIndex
      ? 1
      : 0,
);

Other Implementations

Languages

These libraries should be byte-for-byte compatible.

Language	Repo
Go	https://github.com/rocicorp/fracdex
Python	https://github.com/httpie/fractional-indexing-python
Kotlin	https://github.com/darvelo/fractional-indexing-kotlin
Ruby	https://github.com/kazu-2020/fractional_indexer

Random Jitter

To minimize the likelihood of index collisions when generating fractional indexes concurrently, random jitter can be added to the generated indices. These libraries extend this package's functionality with random jitter.

Language	Repo
TypeScript	https://github.com/nathanhleung/jittered-fractional-indexing