List Ordering

Fractional indexing enables conflict-free list ordering in distributed systems by assigning string-based position values that maintain lexicographic order. This makes it ideal for implementing drag-and-drop reordering in LiveStore applications where multiple clients may reorder items concurrently.

To understand how the algorithm works, see these visual and interactive explanations:

• CRDT Fractional Indexing by Evan Wallace - Visual explanation of the algorithm
• Implementing Fractional Indexing by David Greenspan - Interactive notebook walkthrough

Why Fractional Indexing?

Traditional numeric ordering (1, 2, 3…) requires renumbering multiple items when inserting or reordering, which creates conflicts in distributed systems. Fractional indexing solves this by:

• Generating position values that can always be inserted between any two existing positions
• Using lexicographic string ordering that works naturally with SQL ORDER BY
• Eliminating the need for coordination between clients when reordering
• Avoiding cascading updates when inserting items

For example, inserting a new item between positions “a0” and “b0” generates “aV”, which sorts correctly without modifying existing items.

Installation

Install the fractional-indexing package from Rocicorp (the same team behind Replicache):

pnpm install fractional-indexing

Schema Design

Define a text column to store the fractional index and add a database index for efficient ordering:

schema.ts

import { State } from '@livestore/livestore'

export const task = State.SQLite.table({
  name: 'task',
  columns: {
    id: State.SQLite.integer({ primaryKey: true }),
    title: State.SQLite.text({ default: '' }),
    completed: State.SQLite.integer({ default: 0 }),
    /** Fractional index for ordering tasks in the list */
    order: State.SQLite.text({ nullable: false, default: '' }),
  },
  indexes: [
    /** Index for efficient ordering queries */
    { name: 'task_order', columns: ['order'] },
  ],
  deriveEvents: true,
})

export type Task = typeof task.Type

export const tables = { task }

The order column stores string values like “a0”, “a1”, “aV” that maintain lexicographic ordering. Adding a database index on this column ensures efficient queries when retrieving ordered lists.

Creating Ordered Items

Use generateKeyBetween(a, b) to generate position values when creating new items:

create-item.ts events.ts schema.ts

import { generateKeyBetween } from 'fractional-indexing'

import type { Store } from '@livestore/livestore'

import { events } from './events.ts'
import { tables } from './schema.ts'

declare const store: Store

/** Create a new task at the end of the list */
export const createTaskAtEnd = (title: string) => {
  // Get the highest order value
  const highestOrder = store.query(tables.task.select('order').orderBy('order', 'desc').limit(1))[0] ?? null

  // Generate new order after the highest
  const order = generateKeyBetween(highestOrder, null)

  // Commit the event
  store.commit(events.createTask({ title, order }))

  return order
}

/** Create a new task at the beginning of the list */
export const createTaskAtStart = (title: string) => {
  // Get the lowest order value
  const lowestOrder = store.query(tables.task.select('order').orderBy('order', 'asc').limit(1))[0] ?? null

  // Generate new order before the lowest
  const order = generateKeyBetween(null, lowestOrder)

  store.commit(events.createTask({ title, order }))

  return order
}

/** Create the very first task in an empty list */
export const createFirstTask = (title: string) => {
  // When the list is empty, use a simple default value
  const order = 'a1'

  store.commit(events.createTask({ title, order }))

  return order
}

import { Events, Schema } from '@livestore/livestore'

export const events = {
  createTask: Events.synced({
    name: 'v1.CreateTask',
    schema: Schema.Struct({
      title: Schema.String,
      order: Schema.String,
    }),
  }),
  updateTaskOrder: Events.synced({
    name: 'v1.UpdateTaskOrder',
    schema: Schema.Struct({
      id: Schema.Finite,
      order: Schema.String,
    }),
  }),
}

import { State } from '@livestore/livestore'

export const task = State.SQLite.table({
  name: 'task',
  columns: {
    id: State.SQLite.integer({ primaryKey: true }),
    title: State.SQLite.text({ default: '' }),
    completed: State.SQLite.integer({ default: 0 }),
    /** Fractional index for ordering tasks in the list */
    order: State.SQLite.text({ nullable: false, default: '' }),
  },
  indexes: [
    /** Index for efficient ordering queries */
    { name: 'task_order', columns: ['order'] },
  ],
  deriveEvents: true,
})

export type Task = typeof task.Type

export const tables = { task }

Key patterns:

• generateKeyBetween(highest, null) - Append to end of list
• generateKeyBetween(null, lowest) - Prepend to start of list
• Use "a1" as a simple default for the first item in an empty list

Reordering Items

Handle drag-and-drop by generating a new position between the target boundaries:

reorder.ts events.ts schema.ts

import { generateKeyBetween } from 'fractional-indexing'

import type { Store } from '@livestore/livestore'

import { events } from './events.ts'
import { tables } from './schema.ts'

declare const store: Store

/**
 * Reorder a task by moving it between two other tasks
 *
 * @param taskId - The task to reorder
 * @param beforeOrder - The order value of the task that will be before this one (null if moving to end)
 * @param afterOrder - The order value of the task that will be after this one (null if moving to start)
 */
export const reorderTask = (taskId: number, beforeOrder: string | null, afterOrder: string | null) => {
  // Generate a new fractional index between the two positions
  const newOrder = generateKeyBetween(beforeOrder, afterOrder)

  // Commit the update event
  store.commit(events.updateTaskOrder({ id: taskId, order: newOrder }))

  return newOrder
}

/**
 * Handle drag-and-drop reordering
 *
 * This is a more complete example showing how to handle drag-and-drop
 * with proper boundary checks.
 */
export const handleDragDrop = (draggedTaskId: number, targetTaskId: number, dropPosition: 'before' | 'after') => {
  const before = dropPosition === 'before'

  // Get the target task's order
  const targetOrder = store.query(tables.task.select('order').where({ id: targetTaskId }).first({ behaviour: 'error' }))

  // Find the nearest task in the drop direction
  const nearestOrder =
    store.query(
      tables.task
        .select('order')
        .where({
          order: { op: before === true ? '>' : '<', value: targetOrder },
        })
        .orderBy('order', before === true ? 'asc' : 'desc')
        .limit(1),
    )[0] ?? null

  // Generate new order between target and nearest
  const newOrder = generateKeyBetween(
    before === true ? targetOrder : nearestOrder,
    before === true ? nearestOrder : targetOrder,
  )

  // Commit the update
  store.commit(events.updateTaskOrder({ id: draggedTaskId, order: newOrder }))

  return newOrder
}

import { Events, Schema } from '@livestore/livestore'

export const events = {
  createTask: Events.synced({
    name: 'v1.CreateTask',
    schema: Schema.Struct({
      title: Schema.String,
      order: Schema.String,
    }),
  }),
  updateTaskOrder: Events.synced({
    name: 'v1.UpdateTaskOrder',
    schema: Schema.Struct({
      id: Schema.Finite,
      order: Schema.String,
    }),
  }),
}

import { State } from '@livestore/livestore'

export const task = State.SQLite.table({
  name: 'task',
  columns: {
    id: State.SQLite.integer({ primaryKey: true }),
    title: State.SQLite.text({ default: '' }),
    completed: State.SQLite.integer({ default: 0 }),
    /** Fractional index for ordering tasks in the list */
    order: State.SQLite.text({ nullable: false, default: '' }),
  },
  indexes: [
    /** Index for efficient ordering queries */
    { name: 'task_order', columns: ['order'] },
  ],
  deriveEvents: true,
})

export type Task = typeof task.Type

export const tables = { task }

The generateKeyBetween function automatically creates a string value that sorts lexicographically between the two boundary positions. Pass null to represent the start or end of the list.

Querying Ordered Lists

Query items using standard SQL ordering on the fractional index column:

query.ts schema.ts

import type { Store } from '@livestore/livestore'

import { tables } from './schema.ts'

declare const store: Store

/**
 * Query tasks in their proper order
 *
 * The fractional index values maintain lexicographic ordering,
 * so we can simply order by the 'order' column.
 */
export const getOrderedTasks = () => {
  return store.query(tables.task.select().orderBy('order', 'asc'))
}

/**
 * Get the highest order value (for appending new items)
 */
export const getHighestOrder = (): string | null => {
  const order = store.query(tables.task.select('order').orderBy('order', 'desc').limit(1))[0]

  return order ?? null
}

/**
 * Get the lowest order value (for prepending new items)
 */
export const getLowestOrder = (): string | null => {
  const order = store.query(tables.task.select('order').orderBy('order', 'asc').limit(1))[0]

  return order ?? null
}

import { State } from '@livestore/livestore'

export const task = State.SQLite.table({
  name: 'task',
  columns: {
    id: State.SQLite.integer({ primaryKey: true }),
    title: State.SQLite.text({ default: '' }),
    completed: State.SQLite.integer({ default: 0 }),
    /** Fractional index for ordering tasks in the list */
    order: State.SQLite.text({ nullable: false, default: '' }),
  },
  indexes: [
    /** Index for efficient ordering queries */
    { name: 'task_order', columns: ['order'] },
  ],
  deriveEvents: true,
})

export type Task = typeof task.Type

export const tables = { task }

Since fractional index values maintain lexicographic ordering, you can use simple ORDER BY clauses without special handling.

Best Practices

• Use text/string columns - Fractional index values are strings, not numbers
• Add database indexes - Index the order column for efficient queries
• Validate lexicographic ordering - Ensure your sorting logic uses standard string comparison, not locale-aware comparison (avoid String.prototype.localeCompare())
• Handle empty lists - Use a simple default like "a1" for the first item
• Consider bulk operations - For creating multiple items at once, use generateNKeysBetween(a, b, n) from the same package

Real-World Example

The web-linearlite example demonstrates fractional indexing for Kanban board ordering. It shows:

• Schema definition with kanbanorder column
• Creating issues with proper ordering
• Drag-and-drop reordering across columns
• Querying issues in order by status

Check examples/web-linearlite/src/livestore/schema/issue.ts for the schema and examples/web-linearlite/src/components/column.tsx for the drag-and-drop implementation.

How It Works

Fractional indexing generates position strings that always allow insertion between any two positions:

Initial:  a0    a1    a2
Insert between a0 and a1: a0V (sorts: a0 < a0V < a1)
Insert between a0V and a1: a0n (sorts: a0 < a0V < a0n < a1)

The algorithm ensures:

• Position strings stay reasonably short
• No coordination needed between clients
• Conflicts resolve naturally through lexicographic ordering
• Works seamlessly with LiveStore’s event sourcing model

For more details on the algorithm, see the fractional-indexing documentation.