# 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](https://madebyevan.com/algos/crdt-fractional-indexing/) by Evan Wallace - Visual explanation of the algorithm
- [Implementing Fractional Indexing](https://observablehq.com/@dgreensp/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](https://github.com/rocicorp/fractional-indexing) (the same team behind Replicache):

```bash
pnpm install fractional-indexing
```

## Schema Design

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


## `patterns/list-ordering/schema.ts`

```ts filename="patterns/list-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:


## `patterns/list-ordering/create-item.ts`

```ts filename="patterns/list-ordering/create-item.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
}
```

### `patterns/list-ordering/events.ts`

```ts filename="patterns/list-ordering/events.ts"
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.Number,
      order: Schema.String,
    }),
  }),
}
```

### `patterns/list-ordering/schema.ts`

```ts filename="patterns/list-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 }
```

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:


## `patterns/list-ordering/reorder.ts`

```ts filename="patterns/list-ordering/reorder.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
}
```

### `patterns/list-ordering/events.ts`

```ts filename="patterns/list-ordering/events.ts"
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.Number,
      order: Schema.String,
    }),
  }),
}
```

### `patterns/list-ordering/schema.ts`

```ts filename="patterns/list-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 `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:


## `patterns/list-ordering/query.ts`

```ts filename="patterns/list-ordering/query.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
}
```

### `patterns/list-ordering/schema.ts`

```ts filename="patterns/list-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 }
```

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](https://github.com/livestorejs/livestore/tree/dev/examples/web-linearlite) 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](https://github.com/rocicorp/fractional-indexing).