Modeling Hierarchical Data Structures
1. Using Adjacency List Model
| Aspect | Detail |
|---|---|
| Schema | id, parent_id (self-FK) |
| Insert/Move | O(1) — just update parent_id |
| Read tree | Recursive CTE or app loop |
| Best for | Frequent writes, shallow trees |
Example: Adjacency List
CREATE TABLE categories (
id BIGSERIAL PRIMARY KEY,
name TEXT, parent_id BIGINT REFERENCES categories(id)
);
WITH RECURSIVE t AS (
SELECT id, name, parent_id, 1 AS depth FROM categories WHERE id = 1
UNION ALL
SELECT c.id, c.name, c.parent_id, t.depth+1
FROM categories c JOIN t ON c.parent_id = t.id
) SELECT * FROM t;2. Using Nested Set Model
| Aspect | Detail |
|---|---|
| Schema | id, lft, rgt |
| Descendants | WHERE lft BETWEEN p.lft AND p.rgt |
| Read | O(log n) — fast subtree queries |
| Write | Expensive — re-numbering many rows |
| Best for | Mostly-read trees |
3. Using Path Enumeration Model
| Aspect | Detail |
|---|---|
| Schema | path TEXT (e.g., '/1/4/12/') |
| Descendants | WHERE path LIKE '/1/4/%' |
| Ancestors | Split path into IDs |
| Postgres ltree | Native tree type with operators |
| Best for | Read-heavy, deep trees |
4. Using Closure Table Model
| Aspect | Detail |
|---|---|
| Schema | nodes + closure(ancestor, descendant, depth) |
| Insert subtree | Insert rows for every ancestor pair |
| Query speed | O(1) descendants/ancestors via JOIN |
| Storage | O(n²) worst case |
| Best for | Complex queries, multiple parents (DAGs) |
Example: Closure Table
CREATE TABLE node (id BIGSERIAL PRIMARY KEY, name TEXT);
CREATE TABLE node_closure (
ancestor BIGINT REFERENCES node(id),
descendant BIGINT REFERENCES node(id),
depth INT NOT NULL,
PRIMARY KEY (ancestor, descendant)
);
-- All descendants of node 1:
SELECT n.* FROM node_closure c JOIN node n ON n.id = c.descendant
WHERE c.ancestor = 1 AND c.depth > 0;5. Comparing Hierarchical Models
| Model | Insert | Subtree Read | Move | Storage |
|---|---|---|---|---|
| Adjacency List | O(1) | Recursive CTE | O(1) | Compact |
| Nested Set | O(n) | Range scan | Expensive | Compact |
| Path Enumeration | O(1) | Prefix scan | Update subtree | Medium |
| Closure Table | O(depth) | JOIN O(1) | Rebuild edges | O(n²) |
6. Querying Hierarchical Data
| Need | Pattern |
|---|---|
| All descendants | Recursive CTE / closure JOIN / LIKE on path |
| All ancestors | Walk parent_id up; or closure |
| Depth / level | Recursion counter or stored depth |
| Siblings | WHERE parent_id = N AND id <> self |
7. Modeling Tree Structures
| Tree Type | Best Model |
|---|---|
| Category trees (shallow) | Adjacency list |
| File systems | Path enumeration |
| Org charts | Closure table |
| Comment threads | Path / ltree |
8. Modeling Graph Structures
| Aspect | Detail |
|---|---|
| Edges table | (from_id, to_id, edge_type, weight) |
| Multi-parent | Closure table or recursive CTE |
| Cycles | Track visited set; bounded recursion depth |
| Performance limits | Switch to graph DB (Neo4j) for deep traversals |
| Apache AGE (PG) | Cypher inside Postgres |
9. Handling Hierarchical Data Updates
| Operation | Detail |
|---|---|
| Move subtree | Adjacency: change parent_id; closure: rebuild edges |
| Delete subtree | ON DELETE CASCADE / recursive purge |
| Prevent cycles | BEFORE trigger checks new parent not in descendants |
| Atomic move | Wrap in transaction |
10. Optimizing Hierarchical Queries
| Optimization | Detail |
|---|---|
| Index parent_id | Critical for downward traversal |
| Index path / lft / rgt | Per model |
| Materialize depth | Avoid recomputing |
| Cache hot subtrees | Especially navigation menus |
| Limit recursion depth | Bounded recursive CTE |