Ordering items in a list is a problem that sounds trivial until you’re in a
multiplayer environment. When multiple users can drag, insert, and delete items
at the same time, simple array indexing falls apart quickly.

<Figure
  className="[&>div]:rounded-none"
  caption="Drag-and-drop items in this multiplayer list"
  highlight={false}
>
  <IssuesListDemo />
</Figure>

Fractional indexing is an elegant solution to this problem, often used in
CRDT-based platforms; it’s how collaborative applications like Figma and Linear
order realtime lists, and it’s the way we designed our
[conflict-free sync engine](/docs/collaboration-features/multiplayer/sync-engine/liveblocks-storage#Conflict-free-data-structures).

<IndexDemo variant="fractional-auto" />

Let’s take a look at how it works and some challenges we solved.

## Regular array indexing

In a single-player app, ordering a list isn’t a problem. You have an array, each
item has an index, and when an operation changes the list, the indices update
accordingly. Let’s say you have a list of three items.

<IndexDemo variant="array" />

Picture inserting an item into position `1`. Every item after it has to adjust
its index by 1 to make room for the new value. For example `purple` goes from
index `1` to `2`. A single insert affects every item after its inserted
position.

<IndexDemo variant="array-insert" />

This also occurs when reordering. Drag an item to a new position and multiple
items need a new index.

<IndexDemo variant="array-drag" />

In the log, you can see exactly which items updated on each change.

## The problem with arrays

Regular arrays work fine locally, but in multiplayer every shifted index is a
change that has to travel over the network, greatly increasing the amount of
data that needs to be synched and sent.

<ArrayRippleDemo />

Additionally, when users simultaneously edit the same list, their changes can
conflict, causing the list to diverge.

### Simultaneous editing

Picture Alice inserting an item while Bob deletes another. Each user works from
their own local state, and when the two clients sync, they end up applying each
other’s operations on top of different arrays, resulting in a conflict.

<IndexDemo variant="array-multiplayer-conflict" />

The same thing happens when two users simultaneously add an item. Both clients
“insert at index 1”, but once the operations merge, there’s no canonical order
to agree on.

<IndexDemo variant="array-multiplayer-single" />

In a multiplayer environment, every client needs to converge to the same list,
regardless of the order in which concurrent edits arrive. Each item needs a
stable position of its own, independent of other items.

## What is fractional indexing?

Fractional indexing flips the model. Instead of an index being derived from an
item’s position in a sequence, each item carries its own position value—a value
that naturally sits between its neighbors. It’s easiest to think about these
fractional indices as decimal numbers between `0` and `1`. Below, `red`’s index
is `0.1`.

<IndexDemo variant="fractional" />

Because indices are fractions, an infinite number of values can fit between any
two existing indices—you can always add another point of precision, e.g. between
`0.5` and `0.6` you can pick `0.55`, then `0.555`, and so on. This means _you
only update a single index at a time_, even when moving an item, because there’s
always room for a new value between any two existing indices.

### Inserting an item

When inserting an item, calculate its index by picking the halfway point between
its neighbors. For example, when adding an item between `0.1` and `0.5`, pick
`0.3`.

<IndexDemo variant="fractional-insert" />

To insert an item at the start, pick the halfway point between `0` and the first
item. The same applies in reverse for inserting at the end, with the last item
and `1`.

<IndexDemo variant="fractional-insert-end" />

You’ll notice that when an item is added or removed, every other item is
unaffected. Moving items works the same way, drag an item to a new position and
only one index updates. All others items keep their original position.

<IndexDemo variant="fractional-drag" />

## Fractional indexing solves multiplayer

Because each item’s position is independent, fractional indexing merges
consistently, unlike regular array indexing. Operations are short and
self-contained, only needing a single message to be sent.

<FractionalRippleDemo />

Additionally, both clients can replay each other’s operations and end up with
the same result.

### Simultaneous editing [#fractional-indexing-simultaneous-editing]

If we again imagine Alice and Bob making changes, this time using fractional
positions, changes sync correctly for both clients.

<IndexDemo variant="fractional-multiplayer-conflict" />

When both users add an item at once, they each pick their own fractional
position locally, and the merged list converges on a single order.

<IndexDemo variant="fractional-multiplayer-single" />

### Pushing to the same index

There is an edge case, however. What happens when two users independently pick
the _exact same index_? Both see the new item locally, but after sync each side
orders its own insert before the other’s, and the lists end up in a different
order. We have a conflict.

<IndexDemo variant="fractional-multiplayer-collision" />

A solution for this is to assign each user a unique ID, and append this to their
indices. For example, if Alice’s ID is `001`, and Bob’s is `002`, pushing an
item to index `0.75` would result in `0.75-001` for Alice and `0.75-002` for
Bob.

<IndexDemo variant="fractional-multiplayer-suffix" />

Because no two clients share an ID, no two indices can ever be truly equal, and
both sides converge on the same order. We won’t mention this in the rest of the
article, as it makes explanations more complex, but bear in mind that it’s part
of the solution.

## Indices work better as strings

While decimals work as a mental model, they break down in practice. Floating
point numbers have limited precision, and after enough subdivisions, two
positions quickly become indistinguishable due to rounding. It only takes about
50 inserts at the end of the list to hit the precision limit, breaking the
system.

<IndexDemo variant="fractional-push" />

If these digits are instead stored as strings, the system is much more robust,
and the precision limit won’t be hit.

<IndexDemo variant="fractional-push-strings" />

While there’s no longer a limit, you’ll notice another problem—indices quickly
become large when repeatedly pushing items to the end of a list. We can fix
this.

## Preventing index growth

At Liveblocks, we provide conflict-free lists to companies, which makes us
uniquely positioned to understand how realtime arrays are used in production. We
discovered that customers often repeatedly inserted items into the same position
in the list, causing index lengths to spiral.

### Real world usage

By far, the most commonly used array operation used is push, specifically
pushing items to the end of a list. This can be quite a problem in some apps, as
you can end up with indices that are as long as the values themselves, if not
longer.

```json
"purple" → "0.99999999999999986171875"
"orange" → "0.999999999999999930859375"
"yellow" → "0.9999999999999999654296875"
```

If you have a list with thousands of items, a significant chunk of your data
will be indices, and downloading it is going to slow down your app. Previously,
we’d pick the midpoint for new indices, but for this situation, we use a
different approach.

### Viewport-based index growth

A pragmatic solution we developed for this is something we call
[“viewport-based” index growth](https://github.com/liveblocks/liveblocks/blob/4e055c85e2171b28bdc4532d64a00bc0ac6d63fb/packages/liveblocks-core/src/lib/position.ts#L166-L235).

When users push items to the end of the list, we use a different algorithm to
calculate indices—as soon as the last item in the list needs an extra digit, we
grow the index by 3 characters at once, then only increment one step at a time,
instead of using the halfway point.

For example, after `0.9`, we jump straight to `0.9001`, and then increment by
only `0.0001` at a time for new items.

<IndexDemo variant="fractional-push-viewport" />

Using this new solution, we can keep pushing to the same position without
worrying about the index size. Once the index needs another character, we jump
to another viewport, for example from `0.999` to `0.999001`.

<IndexDemo variant="fractional-push-viewport-nested" />

Note that we skip past `.9000` because trailing zeros aren't allowed—they’d
represent the same value as `.9`.

### Side-by-side comparison

The difference between the two approaches quickly becomes apparent when you
start pushing tens of items to the end of the list. The viewport-based approach
stays reasonable, whereas the naive approach quickly becomes impractical.

<IndexDemo variant="fractional-push-padded-rows" />

Here’s a comparison showing the amount of additionally data used for keys in
each approach.

<IndexDemo variant="fractional-push-padded-charts" />

## A new character set

Another way we can significantly shrink the size of indices is to move away from
decimal numbers and use a new character set, base 96.

### Base 96

Base 96 is a numeral system made up of the 95 printable
[ASCII](https://en.wikipedia.org/wiki/ASCII) characters, starting at the space
character <code>&nbsp;</code> and ending at tilde `~`.

<StringExplorer variant="ascii-table" />

Instead of using decimals as indices, you can use base 96 values instead, such
as `!` and `%`.

<IndexDemo variant="fractional-base95" />

After convering a few values from decimals, the real benefit of base 96 becomes
apparent—only the first 10 characters of the alphabet are used, the same 10
digits decimal gave us.

<MappingAnimation />

The real benefit of using base 96 is when you start using the extra 86 chars,
and which you can slot _between_ decimal values. This way we can represent
values that weren’t expressible in decimal, without having to grow the length of
the string.

### Easy sorting

The above base 96 representation is an elegant solution for indices because
ASCII values can simply be lexicographically compared to define their natural
ordering. Try it with 2 values below.

<Base95ComparisonSlider />

Most languages support string comparison without a custom sort function.

### Smaller indices

Switching from decimal to base 96 results in significantly shorter indices—try
moving the slider to see the difference in an index’s length.

<DecimalToBase95Slider />

With a list containing thousands of items, the savings are significant.

### Base 96 in practice

Let’s try the earlier demos with base 96. Reordering items works the same way;
we’re just storing the base 96 value instead of the decimal. You’ll notice that
the indices are much shorter.

<IndexDemo variant="fractional-drag-base95" />

Pushing new items at the end is no different: each press computes a position
that will be lexicographically greater than the last item. This demo uses the
viewport-based growth algorithm from earlier, now rendered in base 96.

<IndexDemo variant="fractional-push-base95" />

## We’ve already solved this

At Liveblocks, we use fractional indexing inside
[Liveblocks Storage](/docs/collaboration-features/multiplayer/sync-engine/liveblocks-storage),
specifically [`LiveList`](/docs/api-reference/liveblocks-client#LiveList), which
provides a realtime multiplayer array you can use in your app.

```tsx
// Create a list
const squares = new LiveList(["red", "blue"]);

// Run conflict-resolved operations
squares.move(0, 1);
squares.insert("yellow", 1);
squares.delete(2);
```

You can also nest complex data structures inside `LiveList`, such as
[`LiveObject`](/docs/api-reference/liveblocks-client#LiveObject) and
[`LiveMap`](/docs/api-reference/liveblocks-client#LiveMap)—conflict-resolved
objects and maps.

```tsx
// Create a list
const squares = new LiveList();

// Create a complex conflict-resolved object
const square = new LiveObject({
  color: "red",
  coords: new LiveMap({
    x: 100,
    y: 50,
  }),
});

// Add it to the list
squares.push(square);
```

Make a change to any part of your data structure, and it’ll be merged
automatically across all clients.

### Building a real app

Building a realtime list of issues, like in the example below, becomes a trivial
task with Liveblocks Storage.

<Figure
  className="[&>div]:rounded-none"
  caption="Drag-and-drop items in this multiplayer list"
  highlight={false}
>
  <IssuesListDemo />
</Figure>

First, define your data structure in TypeScript, in this case each issue has a
`title`, a `ref`, a `priority`, and an `assignee`.

```tsx
import { LiveList, LiveObject } from "@liveblocks/client";

// Define an issue type
// +++
type Issue = LiveObject<{
  title: string;
  ref: `LB-${number}`;
  priority: string | null;
  assignee: string | null;
}>;
// +++

declare global {
  interface Liveblocks {
    Storage: {
      // Add a LiveList of issues to root storage
      // +++
      issues: LiveList<Issue>;
      // +++
    };
  }
}
```

In React, add [`useStorage`](/docs/api-reference/liveblocks-react#useStorage) to
fetch the realtime issues, and render them on the page.

```tsx
import { useStorage } from "@liveblocks/react/suspense";

function IssuesList() {
  // Get a list of issues
  // +++
  const issues = useStorage((root) => root.issues);
  // +++

  return (
    <main>
      {/* Render the list of issues */}
      // +++
      {issues.map((issue) => (
        <div key={issue.ref}>
          <span>{issue.title}</span>
          <span>{issue.priority}</span>
          {/* ... */}
        </div>
      ))}
      // +++
    </main>
  );
}
```

[`useMutation`](/docs/api-reference/liveblocks-react#useMutation) allows you to
modify your data structures, for example to create a new issue.

```tsx
import { useStorage, useMutation } from "@liveblocks/react/suspense";
import { LiveObject } from "@liveblocks/client";

function IssuesList() {
  // Get a list of issues
  const issues = useStorage((root) => root.issues);

  // Create a new issue and add it the list
  // +++
  const newIssue = useMutation(({ storage }) => {
    const issues = storage.get("issues");

    const newIssue = new LiveObject({
      title: "Untitled",
      ref: `LB-${issues.length + 1}`,
      priority: null,
      assignee: null,
    });

    issues.push(newIssue);
  }, []);
  // +++

  return (
    <main>
      {/* Render the list of issues */}
      {issues.map((issue) => (
        <div key={issue.ref}>
          <span>{issue.title}</span>
          <span>{issue.priority}</span>
          {/* ... */}
        </div>
      ))}
      {/* Button to create a new issue */}
      // +++
      <button onClick={newIssue}>➕ New issue</button>
      // +++
    </main>
  );
}
```

You can even create mutations that modifies deeply nested data structures, for
example one that updates the priority of a specific issue.

```tsx
import { useStorage, useMutation } from "@liveblocks/react/suspense";
import { LiveObject } from "@liveblocks/client";

function IssuesList() {
  // Get a list of issues
  const issues = useStorage((root) => root.issues);

  // Create a new issue and add it the list
  const newIssue = useMutation(({ storage }) => {
    const issues = storage.get("issues");

    const newIssue = new LiveObject({
      title: "Untitled",
      ref: `LB-${issues.length + 1}`,
      priority: null,
      assignee: null,
    });

    issues.push(newIssue);
  }, []);

  // Update the priority of an issue
  // +++
  const updatePriority = useMutation(
    ({ storage }, issueRef: string, priority: string) => {
      const issues = storage.get("issues");
      const issue = issues.find((issue) => issue.ref === issueRef);
      issue.set("priority", priority);
    },
    []
  );
  // +++

  return (
    <main>
      {/* Render the list of issues */}
      {issues.map((issue) => (
        <div key={issue.ref}>
          <span>{issue.title}</span>
          // +++
          <Select
            value={issue.priority}
            onChange={(priority) => updatePriority(issue.ref, priority)}
          />
          // +++
          {/* ... */}
        </div>
      ))}

      {/* Button to create a new issue */}
      <button onClick={newIssue}>➕ New issue</button>
    </main>
  );
}
```

To learn more, check out our
[multiplayer get started guides](/docs/get-started/multiplayer).

## Conclusion

Fractional indexing is a tiny idea with an outsized impact. By giving each item
its own positional value instead of a deriving it from a sequence, you get a
list that merges cleanly across clients, sends minimal data over the network,
and allows concurrent edits to converge without conflicts.

If you’d rather not build fractional indexing from scratch,
[try Liveblocks Storage](/docs/get-started/multiplayer), as we’ve already done
it for you—focus on your app instead of the ordering problem underneath it.