skip to content

In a cloud-drive metadata database, what does renaming a folder with a million descendants cost under a full-path model versus a parent-id model?

level: middleimportance: should knowfreq 50%

answer

  1. where does the path live
  2. descendants share the prefix
  3. children point at an ID
  4. one lookup per level
  5. folder into its own child

basics

~20 s

Storing full paths on every entry makes a folder rename rewrite all million descendant rows, a huge write that is hard to make atomic. Storing parent-id pointers makes it a one-row update, but path resolution then costs one lookup per level.

solid answer

~40 s

In a **full-path model** each row stores `/team/reports/q3/file.pdf`, so renaming `/team/reports` rewrites every descendant's path: a million-row update that is slow, contends with live edits, and can leave the tree half-renamed if it fails. In a **parent-id model** each row stores its `name` and `parent_id`, so the rename changes one row and a move changes one `parent_id`. The price moves elsewhere: resolving `/a/b/c/d.txt` takes one indexed lookup per component, subtree operations need traversal, and every move must be checked so a folder is never placed inside its own descendant. Blob bytes are untouched in both models as long as blob keys are opaque IDs. Most large systems use parent-id as the source of truth and add ID-based APIs and path caches.

code

sql · 9 lines
sql
-- parent-id model: one row changes
UPDATE entries
SET name = 'reports-2026'
WHERE id = :folder_id;

-- full-path model: every descendant changes
UPDATE entries
SET path = '/team/reports-2026' || SUBSTRING(path FROM CHAR_LENGTH('/team/reports') + 1)
WHERE path = '/team/reports' OR path LIKE '/team/reports/%';

go deeper

for a junior

Recall the two ways to record a location: store the whole path string, or store a pointer to the parent folder.

for a middle

Explain why a rename touches every descendant under full paths but one row under parent pointers, and what the parent-id model pays in path lookups and subtree traversal.

for a senior

Bring up the operational edges: non-atomic mass rewrites, contention with live edits, the cycle check on moves, and making that check safe against concurrent moves.

for a principal

Argue for a source of truth plus derived views: parent-id for correctness and instant renames, with ID-based APIs, caches and asynchronously maintained path columns for read-heavy paths.

## The namespace problem Users of a **cloud-drive service** see a tree of folders, but the **metadata database** stores rows. How each row records *where* it lives in that tree decides what a folder rename or move costs. Two classic models exist. - **Full-path model.** Every entry stores its complete path as a string, for example `/team/reports/q3/summary.pdf`, usually with a unique index on that column. - **Parent-id model.** Every entry stores only its own `name` and the `parent_id` of the folder containing it, with a unique index on `(parent_id, name)`. The path is implied by following parent pointers up to the root. ## What a rename costs in each Take a folder `/team/reports` with one million descendants spread through nested subfolders. **Full-path model.** Every descendant's path begins with `/team/reports/`, so all million rows must be rewritten. That write takes a long time, produces a large replication stream, conflicts with users editing inside the folder, and is hard to make atomic: a failure halfway leaves the tree split between old and new prefixes. If those rows live on several database partitions, one transaction may not even be possible. **Parent-id model.** Descendants point at the folder's **ID**, not its name, so only the folder's own row changes. A rename is one row update; a move is one update of `parent_id`. In both models the **file bytes are untouched**, provided blobs are keyed by opaque IDs rather than by path. If blob keys *were* paths, a rename would mean copying and deleting every object, because object stores usually have no rename operation. ```sql -- parent-id model: a rename touches one row UPDATE entries SET name = 'reports-2026' WHERE id = :folder_id; -- full-path model: a rename rewrites the folder and every descendant UPDATE entries SET path = '/team/reports-2026' || SUBSTRING(path FROM CHAR_LENGTH('/team/reports') + 1) WHERE path = '/team/reports' OR path LIKE '/team/reports/%'; ``` ## What the parent-id model gives up Cheap renames are not free: 1. **Path resolution walks the tree.** Opening `/a/b/c/d.txt` takes one index lookup per component: find `a` under the root, `b` under `a`, and so on. Deep trees cost more round trips unless resolved in one recursive query or served from a cache. 2. **Subtree operations need traversal.** Deleting a folder, totalling its size, or checking whether a file lies beneath a shared folder requires walking descendants or ancestors rather than one prefix scan. 3. **Moves need a cycle check.** Moving folder `/a` into `/a/b/c` would detach the subtree into a loop no path reaches. The server must verify the destination is neither the moved folder nor one of its descendants, and must do so atomically with the update, so two concurrent moves cannot jointly create a cycle. | Operation | Full-path model | Parent-id model | |---|---|---| | Rename or move a folder | Rewrite every descendant | Update one row | | Resolve a path to an entry | One index lookup | One lookup per level | | List a whole subtree | One prefix range scan | Recursive traversal | | Prevent moving a folder into itself | Simple prefix check | Ancestor walk, done atomically | ## Common hybrids Production systems usually take the parent-id model as the **source of truth**, because renaming and moving large folders are everyday user actions that must feel instant, then add: - **ID-based APIs.** Clients hold entry IDs after the first resolution, so most calls skip path walking entirely. - **Path caches.** Recently resolved `path -> id` mappings are cached and invalidated when a folder on the path is renamed or moved. - **Derived path columns.** A denormalized path or ancestor list is maintained asynchronously and used for search or subtree scans where slight staleness is acceptable. ## In an interview State the asymmetry crisply: full paths make lookups cheap and renames proportional to subtree size; parent pointers make renames constant-cost and push the cost onto path resolution and subtree traversal. Then mention the cycle check - it is the edge case interviewers most often probe.

  • When moving a folder under the parent-id model, what check must the server make?
    It must confirm the destination is not the moved folder or any of its descendants, by walking the destination's ancestors to the root and looking for the moved ID. The check and the update must be atomic, for example under a lock or in one serializable transaction; otherwise moving A into B and B into A concurrently can each pass the check and together create a detached cycle.
  • How do parent-id designs keep path resolution fast?
    The unique index on `(parent_id, name)` makes each step one index seek, and a recursive query can resolve all steps in one round trip. APIs hand out entry IDs so clients rarely resolve paths again, and a cache of resolved prefixes absorbs repeat lookups, invalidated whenever a folder on the path is renamed or moved.

saying these in an interview costs you the question

  • A folder rename in a full-path model is a single cheap row update.
  • The parent-id model makes every operation cheaper with no downside.
  • Renaming a folder requires copying all of its files' bytes.
  • A move only needs to check that the destination folder exists.
  • Rewriting a million paths row by row is safe while users browse that subtree.