Reordering a list without renumbering it

You've built a kanban board. A user drags a card from the bottom of a column to the second position. It takes them a quarter of a second and no thought at all.

Now: what does your UPDATE statement look like?

This turns out to be one of those problems that seems trivial until you actually write it down, and then quietly turns into a small research project. This post is about why, and about the approach that solves it - how it works underneath, and the decisions that shaped a library I built around it.

If you just want the API, the README covers that. This is the why.

The problem, stated properly

Say each task has an integer position:

A user drags Review to second place. To keep position meaningful you now write:

UPDATE task SET position = 2 WHERE id = 'review';
UPDATE task SET position = 3 WHERE id = 'build';
UPDATE task SET position = 4 WHERE id = 'ship';

Three writes for one drag. And that number isn't fixed - it's proportional to how many items sit below the drop point. On a 500-card backlog, dragging something to the top rewrites 500 rows. Inside a transaction. While other users are dragging their own cards around the same column.

The bug this produces in practice isn't a crash. It's a board that feels sluggish, occasionally deadlocks under concurrent edits, and every so often loses an ordering because two transactions interleaved. The fix is not a better index. The fix is to stop writing rows that didn't move.

The obvious fixes, and where they break

Leave gaps

Number things 1000, 2000, 3000 instead of 1, 2, 3. To insert between the first two, use 1500. One write.

This works beautifully - about ten times. Then you insert between 1000 and 1001 and you're out of room, and you're renumbering the whole column again. You've bought yourself a delay, not a solution. And the delay is shortest exactly where users insert most: the top of the list.

Use floats

Between 1.0 and 2.0 sits 1.5. Between 1.0 and 1.5 sits 1.25. Halving never runs out, mathematically.

Except a double has 52 bits of mantissa, so it runs out after roughly 50 halving. That sounds like plenty until you realize "always drop it at the top" is a completely normal user behavior, and 50 of those is one afternoon. When it breaks, it breaks silently: two rows end up with the same float and the ordering becomes whatever your database's tiebreaker feels like. You get a bug report saying "the cards keep swapping" and no idea why.

Use a linked list

This is the one that feels genuinely clever, so it deserves a proper look. Give every row a next_id - or prev_id and next_id for a doubly-linked version - and ordering becomes a chain of pointers.

It has a real advantage: moving an item is O(1) writes, three rows regardless of list size. Splice the node out, splice it in elsewhere. No renumbering, ever, and no precision to run out of. On paper it beats everything above.

The problem is that you've optimized the write but destroyed the read.

Reading the list is now sequential. To render a column you must start at the head and follow pointers, one at a time. Each query depends on the result of the last, so they can't be parallelized or batched:

• n = 10 → 20 ms of round trips
• n = 100 → 200 ms
• n = 1000 → 2 s

That's at a modest 2ms round-trip time, and it's pure latency - the queries themselves are trivial. You can collapse it into a single recursive CTE, which most people eventually do, but that's still n index lookups walking a chain the planner can't optimize, and it's markedly slower than the one index range scan you'd get from a sort-able column (b-tree).

You can't sort, filter or paginate. This is the part that really hurts. ORDER BY rank LIMIT 50 OFFSET 100 is trivial with a sort-able column. With a linked list there is no expression to sort by, order is implied by traversal, not stored. Want page 3? Walk 100 nodes first. Want "show me only unblocked cards, in order"? You still have to walk the entire chain and filter in application code, because the chain doesn't survive a WHERE clause.

A single bad write corrupts the whole column. A rank is self-contained: one wrong value misplaces one card. A pointer chain is a shared structure. One dropped update and the list forks, or worse, cycles - and now your rendering loop hangs. Recovery means reconstructing an order that no longer exists anywhere.

Concurrency is genuinely nasty. Two users moving different cards can touch the same neighbor rows, so correctness needs locking across three rows per move. Under real board traffic that's where deadlocks live.

The trade is clean once you see it: linked lists make writes cheap and reads expensive. Fractional ranks make writes cheap and keep reads a plain indexed sort. Since a board is read constantly and reordered occasionally, that's the trade you want.

Just store an array of IDs

Keep the whole order in one column - a JSON array of IDs on the parent row, reordered in application code.

Beautifully simple, and fine for genuinely small, single-user lists. It falls apart on concurrency: the entire order lives in one row, so every reorder is a read-modify-write of that row and two simultaneous edits mean one silently overwrites the other. You've turned every drag into a lock on the whole column. It also breaks the moment you want to query items independently, because the ordering isn't a property of the items at all.

Use a timestamp

Sort by created_at, or a sort_key you bump on move. Works right up until someone needs to insert between two items, at which point you're back to needing a value between two values, and you've reinvented the float problem with worse ergonomics.

They all fail the same way. Ordering needs a value between any two values, and every fixed-precision number, pointer chain, or shared array runs out of somewhere to put it.

The idea: make the rank a string

Here's the shift. Take these two strings:

"a" and "c"

What sorts between them? "b". Fine - that's just integers with extra steps.

But now take these:

"a" and "b"

Nothing sorts between them... if you're only allowed one character. But strings aren't fixed-length. "ab" sorts after "a" and before "b". And "aab" sorts between "a" and "ab". And so on, forever.

That's the whole insight:

A string has no fixed precision. When you run out of room between two strings, you make one of them longer.

And the second half, which makes it practical: databases already sort strings lexicographically. You don't need a custom collation, a stored procedure, or an application-side sort. ORDER BY rank just works.

So a "rank" is a string. Inserting between two items means finding a string that sorts between their two ranks. That's the entire library.

Anatomy of a rank

Here's what one looks like:

• 0|UUUUUU:
• 2|AbCdEf:123
• 1|Fj236e:x23fvtysdg

Three parts:

The bucket is a single digit, 0 to 2, giving the whole scheme extra headroom at the ends.

The major is the workhorse - a fixed-width, 6-character number in base 62 (0-9, A-Z, a-z). Six characters of base 62 gives 62⁶ = 56,800,235,584 distinct values. That's the integer space, and it's enormous.

The minor is the fraction. It's empty most of the time. It only appears when the integer space between two neighbors has been used up, and it is unbounded*, meaning it can grow as long as it needs to.

Why base 62?

Because it's the largest alphabet where lexicographic order matches numeric order using characters that are safe everywhere - no escaping, no encoding surprises, no case-sensitivity landmines in URLs or filenames.

That ordering property is the thing that matters. 0 < 1 < ... < 9 < A < B < ... < Z < a < ... < z is true both as ASCII and as digit values. So string comparison is numeric comparison. Free.

Why fixed width?

This is the trap that catches every first implementation. Consider ordinary numbers as strings:

"9" vs "10"

Numerically 9 < 10. Lexicographically "9" > "10", because '9' comes after '1'. Your ordering is wrong the moment you cross a digit boundary.

Padding to a fixed width fixes it:

"09" vs "10" -> correct

So the major is always exactly six characters. 000000 through zzzzzz, zero-padded. Never five, never seven. That constraint is what lets plain string comparison be correct, and it's why the format looks slightly odd at first glance.

The minor doesn't need padding, because it's a suffix - a longer string that shares a prefix always sorts after the shorter one, which is exactly the fraction semantics we want.

* Unbounded does not mean free, there is a always a price to pay. For minors, the longer they are, the more space they occupy for storage in your database, effectively increasing the space complexity.

Two ways to make a rank

This is the part I'd most like you to take away, because it's the one thing that's genuinely easy to get wrong.

There are two operations, and they are not interchangeable.

Building: rankAfter

When you're creating a fresh list, or appending to the end of one:

import { firstRank, rankAfter } from "@theyoungwolf/lexorank";

let tasks = [{}, {}, {}, {}, {}] // Five task objects

let rank = firstRank(); // 0|UUUUUU:

for (const task of tasks) {
  task.rank = rank; // Assigns first rank to first task and then iterates
  rank = rankAfter(rank); // Generates a step-up rank 
}

console.log(tasks)

Which gives you:

{ "rank": 0|UUUUUU: }
{ "rank": 0|UUYgdW: }
{ "rank": 0|UUcsmY: }
{ "rank": 0|UUh4va: }
{ "rank": 0|UUlH4c: }

Notice firstRank() starts in the middle of the space, not at the bottom - think of it like ("z" - "0") / 2 = "U". That leaves room to prepend later. And each step moves by a fixed amount - one million units of the major - so consecutive items sit far apart, with deliberate empty space between them, to allow you to rank between them.

That structural gap is the whole point. It's the runway for future insertions.

Inserting: rankBetween

When you're placing an item relative to its neighbors:

import { rankBetween } from "@theyoungwolf/lexorank";

const rank = rankBetween(before, after);

This finds the midpoint of whatever gap exists between the two.

Why you can't just use rankAfter to insert

Here's the failure, concretely. Take the first two items from the list above:

A = 0|UUUUUU:

B = 0|UUYgdW:

You want to drop a card between them. rankAfter(A) sounds right - you want it after A, don't you?

rankAfter("0|UUUUUU:");   // which is.. "0|UUYgdW:" 

Now if you look closely, what you have ended up getting for a "new" card is exactly what is B, character for charter - whereas your intent was to place the card between A and B.

B was created by rankAfter(A). The function is a pure function of its single argument - it has no idea anything already follows A. So it hands back the same answer it gave last time, and you've just written a rank that collides with an existing row.

rankBetween reads both sides, so it can't do that:

rankBetween(A, B);   // "0|UUWUUU:"  — genuinely between 0|UUUUUU: and 0|UUYgdW:

And the next insert at the same visual position sees a different pair of neighbors, because the previous insert is now one of them:

rankBetween(A, "0|UUWUUU:");   // "0|UUVUUU:"  — different again - genuinely between 0|UUUUUU: and "0|UUWUUU:"

The rule: rankAfter and rankBefore are for the ends of a list, where nothing exists beyond them. rankBetween is for everywhere else. If you remember one thing from this post, that's it.

Demo it yourself

Watching it subdivide

Insert repeatedly between the same two neighbors and you can watch the major march downward:

Each one lands halfway between A and the previous result. The digits shift rightward as the gap narrows - exactly like halving a decimal, but in base 62

When the integer space runs out

Keep going. After 15 inserts at that same spot, something changes:

0|UUUUUU:U

There it is - the minor. The integer space between those two neighbors is exhausted, so the algorithm switches to the fraction and appends a character after the colon.

And now it genuinely never runs out. :U can become :UU, then :UUU. There's always another character to add.

This is why the earlier float approach fails and this one doesn't. A float's precision is a hardware constant. A string's precision is however many bytes you're willing to store.

The trade is that the rank gets longer. We'll come back to that, honestly, further down.

The decisions

Everything above is the mechanism. What follows is the part that's actually interesting - the choices that aren't forced by the maths, where a library has to take a position.

Open bounds step instead of halving

When you drop something at the very top of a list, there's no item above it. Naturally you write:

rankBetween(null, firstItem);

The obvious implementation treats null as "the bottom of the space" and returns the midpoint between the floor and firstItem. Correct, but also terrible usage of space.

Because the midpoint of that gap halves the remaining space every single time. Repeatedly moving cards to the top exhausts it after about 669 operations. Not 669 per user, not 669 per day - 669 total, for that column, forever. On a busy backlog where "bump this to the top" is the most common gesture there is, that is absolutely reachable.

So the library doesn't do that. A null bound means nothing exists on that side, which means there's no neighbor to collide with, which means the cheap fixed step is safe:

Same call, same ergonomics, 28,590 operations instead of 669. A 43× improvement from noticing that one of the arguments was null.

The rule that makes this coherent rather than a special case: an open bound steps, a closed bound subdivides. Because a closed bound means there's a real row on the other side, and that's precisely when you need the midpoint's collision-safety.

Trailing zeros are illegal, and the reason is unusual

Look at these two ranks:

0|ABCDEF:U

0|ABCDEF:U0

They're different strings, so a database will happily store both. And :U sorts before :U0, so they even have a well-defined order.

Now try to insert between them.

Any rank greater than :U must extend it - it has to start with :U and add something. But every extension of :U also sorts above :U0, because 0 is the smallest character in the alphabet and nothing sorts below it. So there is no string that fits. Not "the algorithm can't find one" - none exists. The gap is provably, mathematically empty.

Two rows sitting next to each other that can never be separated. Your users just can't drop a card there, and nothing in the error message would explain why.

The fix is to make that state unrepresentable: a minor may not end in 0. :U0 is simply not a valid rank, rejected on parse. The library never generates one - the internals guarantee it - so this only ever affects hand-written data or a migration from somewhere else. There's a hasTrailingZero helper for auditing an existing column before you switch over or migrate from existing ranks.

I like this decision because the problem is invisible until you go looking for it, and the fix is a one-line regex change that eliminates an entire class of unfixable data.

Duplicate bounds throw, rather than returning something plausible

What should happen here?

rankBetween("0|ABCDEF:", "0|ABCDEF:");

Two rows share a rank. There's no order between them, so "between them" isn't a place. The tempting implementation is to return something - subdivide the fraction, hand back 0|ABCDEF:U, move on. It's deterministic, it's a valid rank, nothing crashes.

But look at where it lands: after both of them. The user dropped a card between two rows and it appeared below both. That's a visible misplacement, delivered silently, with the underlying data corruption left exactly as it was.

So the library throws DuplicateRankError instead, carrying the offending rank. Duplicate ranks are a data-integrity problem, not a transient hiccup - the honest response is to surface it:

try {
  task.rank = rankBetween(before, after); // both are same
} catch (error) {
  if (error instanceof DuplicateRankError) {
    await rebalanceColumn(columnId);   // fix the cause, then retry
  } else {
    throw error;
  }
}

The general principle: when a function can't honor its contract, saying so beats improvising.

One guarantee, checked at runtime

That contract is worth stating precisely, because the library only makes one promise:

Every rank returned sorts strictly after prev, strictly before next, and strictly after the rank before it in a batch.

No exemptions, no special cases. And it isn't just asserted in the docs - it's verified on every single call, before the value is handed back. Two string comparisons; the cost is nothing.

That sounds like belt-and-braces paranoia. It has already earned its place: it caught a genuine bug where asking for a rank below the lowest possible rank returned a value that sorted above the bound. That's the kind of failure that would otherwise reach production and manifest as "sometimes a card appears in the wrong place," which is approximately the worst bug class there is - intermittent, data-dependent, and invisible in code review.

Batch size caps at 60, and the number isn't arbitrary

You can place several ranks at once:

ranksBetween(3, low, high);
// ["0|FUUUUU:", "0|UUUUUU:", "0|jUUUUU:"]

The cap is 60. It looks like a magic number, it seems quite low as well - just 60 ranks?!?; it's arithmetic. Placing n items between two characters needs at least one whole character per item, and the widest possible gap - 0 to z - spans 61 steps. So 61 / (n + 1) ≥ 1 requires n ≤ 60. Ask for 61 and there is no depth at which they'd fit, at all.

One caveat worth knowing: results are spread across the gap but not exactly evenly. The interval is divided at a single character position and the remainder lands in the final gap, so with larger counts the last gap can be noticeably wider. Every gap is still billions of units across, so it changes nothing in practice - but "equidistant" would have been a promise the function doesn't keep, which is why it isn't called that.

Buckets

The leading digit is extra headroom. When rankAfter exhausts the integer space at the top of bucket 0, it rolls into the middle of bucket 1 rather than failing. rankBefore rolls the other way.

Three buckets gives roughly 86,000 consecutive appends before the fraction is touched at all. For a single ordered list that's an enormous number - and if you ever get near it, the list has outgrown flat ranking and wants partitioning, not a bigger number.

The limitation, stated plainly

Every fractional-ranking scheme has the same weak spot, and I'd rather put it in the middle of the post than bury it: repeatedly inserting between the same two neighbors makes the rank longer.

The important question is whether that happens in real use. So I measured it - 20,000 operations against a 40-card column, under different usage patterns:

Only the last one grows. Realistic boards barely touch the fraction, and the reason is that structural gap: one million units absorbs about fifteen subdivisions before a fraction digit appears, and that headroom regenerates as items move around. Real users don't drop everything in the same crack repeatedly - they spread out, and the space recovers.

When it does grow, it grows predictably - roughly one digit per five insertions:

after   1 insert  at the same spot: minor is  1 digit
after  10 inserts at the same spot: minor is  2 digits
after  50 inserts at the same spot: minor is 10 digits
after 100 inserts at the same spot: minor is 20 digits
after 300 inserts at the same spot: minor is 60 digits

There's a configurable ceiling, defaulting to 128 digits, past which the library raises RankSpaceExhaustedError rather than letting your rank column grow without bound:

Set it per call if your storage or rebalance cadence wants something different:

rankBetween(before, after, { maxMinorLength: 64 });

Think of it as a tripwire, not a budget. Ordinary ranks are 9–13 bytes with a minor of zero. A column whose deepest rank has run to a couple of dozen digits is telling you something. Its telling you the tree has become lob-sided well before anything throws.

Catch it before it throws

There's a minorLength helper for exactly this — it turns the cliff into a gradient:

import { minorLength } from "@theyoungwolf/lexorank";

const deepest = Math.max(...column.map((task) => minorLength(task.rank)));

if (deepest > 24) {
  await rebalanceColumn(columnId);   // call your own rebalance utility in the background, before a user hits the wall
}

Run that in cron job. Nobody ever sees an error.

Rebalancing, and why the obvious version is wrong

Rebalancing resets a list: fresh ranks, evenly spaced, no fraction.

const tasks = await db.task.findMany({
  where: { columnId },
  orderBy: { rank: "asc" },
});

const fresh = rebalance(tasks.length);

await db.$transaction(
  tasks.map((task, i) =>
    db.task.update({ where: { id: task.id }, data: { rank: fresh[i] } }),
  ),
);

It takes a count, not the old ranks, which surprises people. But a rebalance discards the old values entirely - only position in the sorted order carries over. Asking for the ranks would be asking for input the function doesn't use.

Now, the interesting bit. When I built this, my instinct was to spread the items across the entire rank space - maximum room between every pair, which is what a rebalance is for, right?

I measured both. My instinct was wrong:

Even spreading buys you under 2× more room between items, and demolishes the runway past the ends - from twenty-eight thousand appends down to about fifty. Since appending to a list is far more common than subdividing it, that's a bad trade dressed up as an optimization.

So rebalance uses exactly the same spacing as firstRank() + rankAfter(). A rebalanced list is indistinguishable from a freshly built one, which is also a much easier property to reason about.

I mention this mostly because it's a good reminder that "obviously better" and "measurably better" are different things, and the gap between them is where interesting bugs live.

A rebalanced list is indistinguishable from a freshly built one

Concurrency: the honest answer

The algorithm is deterministic. That's a feature - same inputs, same rank, always testable. It also means:

// Two clients, same instant, same neighbours
clientA: rankBetween(a, b);   // "0|UUWUUU:"
clientB: rankBetween(a, b);   // "0|UUWUUU:"  — identical

Two users dropping a card in the same slot at the same moment derive the same rank. That's a collision, and no ranking algorithm can prevent it, because neither client knows the other exists.

The real fix lives in your database: a unique constraint on (column_id, rank), and a retry on violation. The retry re-reads the neighbors, sees the other client's row, and lands somewhere new.

For extra separation there's generateEntropy, which returns a uniformly random Base-62 string that's guaranteed to stay canonical when appended to a rank:

import { generateEntropy } from "@theyoungwolf/lexorank";

generateEntropy();    // "k7Q"
generateEntropy(8);   // "CiXr6ZgS"

Worth knowing what it does and doesn't do: appending widens a rank rather than preserving its position. It reduces collision probability; it doesn't replace the constraint.

Putting it together

Here's the shape of a real implementation.

Assigning ranks when seeding:

import { rebalance } from "@theyoungwolf/lexorank";

const ranks = rebalance(tasks.length);
await db.task.createMany({
  data: tasks.map((task, i) => ({ ...task, rank: ranks[i] })),
});

Reading a column:

const tasks = await db.task.findMany({
  where: { columnId },
  orderBy: { rank: "asc" },   // plain string sort — no custom collation
});

Handling a drop:

import { rankBetween } from "@theyoungwolf/lexorank";

export async function moveTask(taskId: string, columnId: string, targetIndex: number) {
  const column = await db.task.findMany({
    where: { columnId },
    orderBy: { rank: "asc" },
    select: { id: true, rank: true },
  });

  // Ignore the dragged card when working out its new neighbours
  const others = column.filter((task) => task.id !== taskId);

  const before = others[targetIndex - 1]?.rank ?? null;
  const after = others[targetIndex]?.rank ?? null;

  const rank = rankBetween(before, after);

  return db.task.update({ where: { id: taskId }, data: { rank, columnId } });
}

One UPDATE. One row. Regardless of whether the column holds five cards or five thousand.

Optimistic UI, which this design makes pleasant - when the rank is computed on the client, you can reorder locally and reconcile later:

function onDragEnd(result: DropResult) {
  const before = items[result.destination.index - 1]?.rank ?? null;
  const after = items[result.destination.index]?.rank ?? null;

  const rank = rankBetween(before, after);   // instant, no round trip

  setItems((current) =>
    [...current.map((i) => (i.id === result.draggableId ? { ...i, rank } : i))]
      .sort((a, b) => compareRanks(a.rank, b.rank)),
  );

  void api.moveTask(result.draggableId, rank);   // fire and forget
}

The card moves the instant the user releases it. No spinner, no waiting on a server that would otherwise have to renumber four hundred rows.

On testing this sort of thing

One closing thought, because ordering bugs have a nasty property: a wrong rank is still a valid rank. It parses, it sorts, it looks entirely plausible. It just puts a card in the wrong place, occasionally, depending on data you can't reproduce.

Example-based tests are close to useless against that. The trailing-zero problem I described earlier passed every hand-written test I had. It only surfaced under a randomized property search over roughly 280,000 generated bound pairs, asserting prev < result < next every time - 405 violations, every single one with an upper bound ending in 0. That's how the rule got written.

Which is why the runtime invariant check stayed in the shipped library rather than being a test-only thing. If a future change ever produces a rank outside its bounds, it fails loudly at the call site instead of quietly writing a bad row.

Wrapping up

The core idea is small enough to hold in your head: make the rank a string, because strings have unbounded precision and databases already sort them. Everything else - the fixed-width major, base 62, the fraction, the buckets - is machinery in service of that.

The decisions that took the longest weren't about the algorithm. They were about what to do when the algorithm can't help: what happens between two identical ranks, what happens below the lowest possible rank, what happens when a value is technically well-formed but mathematically un-insertable. In every case the answer turned out to be the same - refuse clearly rather than improvise plausibly.

Go ahead, play around with it!

# Zero dependencies, ESM and CommonJS, fully typed.
npm install @theyoungwolf/lexorank