Adjacency List versus Nested Set for hierarchies

WHAT THIS TESTS The interviewer wants you to weigh read-heavy versus write-heavy hierarchy workloads and pick the storage model whose costs match the access pattern.

A GOOD ANSWER COVERS The adjacency list stores each node with a parent_id pointing to its parent. Inserting, deleting, or moving a node changes just one row, so writes are cheap and intuitive. The cost is reads: fetching an entire subtree of arbitrary depth requires recursion, traditionally many queries or a recursive common table expression. The nested set assigns each node a left and right number from a depth-first traversal; a node's descendants are exactly those whose left and right fall between the parent's bounds. This makes a full-subtree read a single indexed range query with no recursion. The cost is writes: inserting or moving any node shifts the left and right values of many other nodes, often half the tree, which is expensive and lock-heavy.

COMMON WRONG ANSWERS Claiming adjacency lists cannot read subtrees at all, ignoring recursive CTEs. Treating nested sets as universally better while glossing over their brutal update cost. Forgetting alternatives like materialized path or closure tables that blend the strengths.

LIKELY FOLLOW-UPS How does a recursive CTE traverse an adjacency list? What is a closure table and when does it win? How do you index nested-set bounds? Which model suits a mostly-read category tree versus a frequently reorganized one?

ONE CONCRETE EXAMPLE For a product catalog read on every page but rarely restructured, nested set gives single-query subtree reads. For a user-editable folder tree reorganized constantly, the adjacency list keeps moves to one row, and a recursive CTE handles the occasional deep read.