Hierarchies in Backend Design · Lesson 4

The move endpoint

One operation, and it collides with every other lesson at once: storage cost, aggregate boundary, authorisation, concurrency, derived data, and an axis you haven't met yet.

1. The race that no single-transaction check catches

The guard that isn't enough

Every move implementation starts with the obvious guard: reject if the destination is the node itself or one of its descendants, because that detaches the branch from the root. Correct, necessary, and insufficient.

PostgreSQL's default isolation level is READ COMMITTED, under which each statement sees the data committed when that statement began. So:

Neither transaction did anything wrong. Each validated against a state that was true when it looked, and the combination is invalid — the textbook write skew: two transactions read an overlapping set, write disjoint rows, and jointly break a constraint neither could see alone. Note that no foreign key can catch this, and re-reading inside the transaction cannot either.

Two fixes, and the scope each protects

You should be able to name both:

• SERIALIZABLE isolation. Postgres's serialisable snapshot isolation detects the read-write dependency cycle and aborts one transaction with a serialisation failure. Correct, requires no new concepts — but the caller must be prepared to retry, and you have to actually set it for this transaction.
• Serialise moves per tree. Take a lock keyed on the tree's root before validating: SELECT pg_advisory_xact_lock(hashtext(root_id)). Now only one move per tree runs at a time, so check-then-act is safe. The reason this is cheap is a fact from Lesson 1's matrix: moves are rare compared to reads. You are serialising the rare operation.

The transferable shape: when an invariant spans rows that no single row's constraint can express, you need either a serialisable transaction or an explicit lock whose scope is the invariant's scope. Choosing the scope is the design work — lock the tree, not the table (kills throughput) and not the node (doesn't cover the invariant).

2. The write itself

Materialised path: one statement

Under a materialised path, one statement covers the whole subtree (Lesson 1 Ex 3):

UPDATE node SET path = $newParentPath || subpath(path, nlevel($oldPath) - 1)
WHERE path <@ $oldPath;

Closure table: disconnect, then cross-join

Under a closure table, the canonical move is a delete and an insert. Worth being able to read, because it looks cryptic and is actually simple: disconnect the subtree from its old ancestors, then connect every old-ancestor-free pair to the new ones.

-- 1. remove links from the subtree's nodes to their former ancestors
DELETE FROM closure
WHERE descendant_id IN (SELECT descendant_id FROM closure WHERE ancestor_id = $node)
  AND ancestor_id  IN (SELECT ancestor_id  FROM closure WHERE descendant_id = $node
                                                          AND ancestor_id <> $node);

-- 2. cross-join new ancestors with the subtree
INSERT INTO closure (ancestor_id, descendant_id, depth)
SELECT a.ancestor_id, d.descendant_id, a.depth + d.depth + 1
FROM closure a, closure d
WHERE a.descendant_id = $newParent AND d.ancestor_id = $node;

That cross join is the |subtree| × |ancestor path| row count from Lesson 1's matrix, made concrete. Both statements plus the parent_id update belong in one transaction — the derived structure must never be observable in a state that disagrees with the truth.

3. The other axis: where among its siblings?

Here is the thing most designs miss until the UI ticket arrives. parent_id answers "whose child am I?" It says nothing about order, and users who drag things expect to drop them between two others.

Why an integer position column fails

The naive answer is an integer position column, which fails the same way nested set fails: inserting at position 3 among 500 siblings renumbers 497 rows, and two concurrent inserts at the same position produce duplicates or lost updates.

Fractional indexing: one row per reorder

Fractional indexing is the fix, and it is how Figma and Linear order sibling sequences. Give each node a sort key drawn from a densely ordered set, and to insert between two neighbours, pick a key strictly between theirs. Figma's original formulation uses a real number — the average of the two neighbours' indices. String keys (the family often called LexoRank) are the practical version, exploiting a property integers lack: between any two strings there is always another string.

siblings:  a0        a1        a2
drop between a0 and a1  →  key = 'a0V'      // one row written, no neighbours touched
drop between a0 and a0V →  key = 'a0G'      // still one row

Every reorder writes exactly one row, regardless of sibling count, and concurrent reorders at different positions don't interact at all.

The two costs

• Keys grow. Repeatedly inserting into the same gap lengthens the key by roughly a character each time. Harmless for a long while; eventually you want a background rebalance that redistributes keys evenly.
• Concurrent inserts into the same gap can generate the same key. Two users both computing "between a0 and a1" both get a0V. Order by (sort_key, id) so ties resolve deterministically rather than arbitrarily per query.

Note the pattern repeating: integer position is nested set, and fractional indexing is adjacency list — dense encodings make reads trivial and writes global; sparse ones make writes local. Third time this trade has appeared, on a different axis each time. That's the web forming.

4. Two authorisation checks, not one

A move is a removal from one parent and an insertion into another. Both need permission. Almost every first implementation checks only the node being moved — which is how a user with read-only access to a shared destination folder writes into it anyway, and how the cross-tenant graft from Lesson 2 §3 arrives through a different door.

Two more preconditions

These belong here too, because move is where they get violated: the resulting depth must stay within your maximum (someone will build a 500-deep chain and break every recursive read), and the destination must be in the same tenant and, usually, the same tree root.

5. Express the command as desired state

Compare two payloads:

POST /nodes/n1:move { "newParentId": "n7" }   // desired state — naturally idempotent
POST /nodes/n1:move { "direction": "up" }     // delta — retry moves it twice

The first can be retried freely: applying "your parent is n7" twice leaves the same tree, so a network timeout followed by a retry is harmless even before you add an idempotency key. The second is a delta, and a retried delta is a double application. This is the cheapest correctness win in API design — prefer desired state over deltas — and it generalises far beyond trees.

Retries and the response

Add the Idempotency-Key header anyway (Lesson 3 §4), because the caller also wants the same response on retry, including the affected count. Return the moved node plus how many descendants came with it; the UI needs it, and it's the number that makes the operation auditable.

Exercises

Exercise 1 — Sequence: order the steps of a safe move

Click the steps in the order they must happen. Wrong slots turn red.

Exercise 2 — Bug hunt: click the offending line

async function moveNode(user: User, nodeId: string, newParentId: string) {  return db.$transaction(async (tx) => {    const node   = await tx.node.findFirstOrThrow({ where: { id: nodeId,      tenantId: user.tenantId } });    const parent = await tx.node.findFirstOrThrow({ where: { id: newParentId, tenantId: user.tenantId } });    await assertCanWrite(user, node);    if (isPrefixOf(node.path, parent.path)) throw new BadRequest('cannot move into own subtree');    await tx.node.update({ where: { id: nodeId }, data: { parentId: newParentId } });    await tx.$executeRaw`UPDATE node SET path = ${parent.path} || subpath(path, nlevel(${node.path}) - 1)                         WHERE tenant_id = ${user.tenantId} AND path <@ ${node.path}`;    await tx.outbox.create({ data: { type: 'NodeMoved', nodeId, newParentId } });  });}

Exercise 3 — Bug hunt: click the offending line (or declare it clean)

Reordering a node among its siblings, fractional-indexing style.

async function reorder(user: User, nodeId: string, afterId: string | null, beforeId: string | null) {  return db.$transaction(async (tx) => {    const [after, before] = await Promise.all([      afterId  ? tx.node.findFirstOrThrow({ where: { id: afterId,  tenantId: user.tenantId } }) : null,      beforeId ? tx.node.findFirstOrThrow({ where: { id: beforeId, tenantId: user.tenantId } }) : null,    ]);    const key = keyBetween(after?.sortKey ?? null, before?.sortKey ?? null);    await tx.node.update({ where: { id: nodeId }, data: { sortKey: key } });  });}

Exercise 4 — Execution (free)

Your sibling keys are a0, a1, a2. A user drags an item between a0 and a1 thirty times in a row, always into the topmost gap. Describe what happens to the keys, what eventually goes wrong, and what you do about it. Then: why is this still better than an integer position column?

Retention

• The sentence to keep: a move is a removal and an insertion — so it needs two authorisation checks, and it races against other moves in a way no constraint can catch.
• Interleave deliberately: "position vs fractional key" and "nested set vs adjacency list" are the same trade on different axes. Next time you meet a dense encoding, predict the write cost before reading about it.
• Tomorrow: reconstruct §1's race from memory as a sequence of four steps, then name both fixes and the scope each one protects.