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.

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

1import { generateKeyBetween } from 'fractional-indexing';
2
3const first = generateKeyBetween(null, null); // "a0"
4
5// Insert after 1st
6const second = generateKeyBetween(first, null); // "a1"
7
8// Insert after 2nd
9const third = generateKeyBetween(second, null); // "a2"
10
11// Insert before 1st
12const zeroth = generateKeyBetween(null, first); // "Zz"
13
14// Insert in between 2nd and 3rd (midpoint)
15const 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.

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

1import { generateNKeysBetween } from 'fractional-indexing';
2
3const first = generateNKeysBetween(null, null, 2); // ['a0', 'a1']
4
5// Insert two keys after 2nd
6generateNKeysBetween(first[1], null, 2); // ['a2', 'a3']
7
8// Insert two keys before 1st
9generateNKeysBetween(null, first[0], 2); // ['Zy', 'Zz']
10
11// Insert two keys in between 1st and 2nd (midpoints)
12generateNKeysBetween(second, third, 2); // ['a0G', 'a0V']

Other Languages

These should be byte-for-byte compatible.

Language	Repo
Go	https://github.com/rocicorp/fracdex
Python	https://github.com/httpie/fractional-indexing-python