Choosing the Right Hierarchical Data Model: Adjacency List, Path Enumeration, Nested Set, or Closure Table

Adjacency List Overview

When designing a database, a common approach for hierarchical data is the adjacency list, which adds a parent_id column to represent the parent of each row (e.g., regions: country, province, city, district). This design works well when the hierarchy depth is fixed and queries only need direct parent/child relationships.

However, the adjacency list struggles with queries that require all descendants of a node, as recursive queries become complex and often limited to two levels.

Path Enumeration

Path enumeration replaces parent_id with a path column (e.g., 1/4/5/7) that stores the full ancestry path using a delimiter such as ‘/’. By comparing path strings with LIKE, you can retrieve ancestors or descendants of any depth.

Example queries:

Find ancestors of comment #7:

WHERE path LIKE '1/4/5/%' OR path LIKE '1/4/%' OR path LIKE '1/%'

Find all descendants of comment #4: WHERE path LIKE '1/4/%' Path enumeration is simple to insert (copy the parent’s path and append the new node’s ID) but has drawbacks: the database cannot enforce path integrity, the application must maintain correct strings, and varchar length limits restrict unlimited tree depth.

Nested Set

The nested set model stores two numbers ( nsleft and nsright) for each node, representing the node’s position in a depth‑first traversal. All descendants have nsleft greater than the parent’s nsleft and nsright less than the parent’s nsright.

With these values you can retrieve an entire subtree or all ancestors with a single range query. Inserting or moving nodes requires recalculating left/right values for many rows, making updates more complex.

Nested sets excel at fast read‑only queries (e.g., retrieving a whole subtree) but are costly for frequent inserts, deletes, or moves.

Closure Table

The closure table stores every ancestor‑descendant pair in a separate table (e.g., tree_paths), including a self‑reference for each node. This makes finding ancestors or descendants a straightforward equality query.

To add a leaf node, insert a self‑reference row, then insert rows linking the new node to all its ancestors. Deleting a node or an entire subtree involves removing the corresponding rows from the closure table.

Closure tables provide the most flexible and direct queries, support multiple trees, and can be optimized further by adding a path_length column to differentiate direct parents from deeper ancestors.

Comparison of Designs

Adjacency list is the simplest and familiar to most developers.

If the DB supports recursive CTEs (WITH) or CONNECT BY PRIOR, adjacency list queries can be efficient.

Path enumeration visualizes ancestry clearly but lacks referential integrity and can be storage‑inefficient.

Nested set offers high query performance for read‑heavy scenarios but makes inserts and moves complex.

Closure table is the most general solution, allowing multiple trees and direct ancestor/descendant queries at the cost of an extra table.

Choosing the Right Design

The optimal design depends on which operations dominate your application. If you need fast, simple reads of whole subtrees, nested set or closure table are preferable. If inserts and deletes are frequent, path enumeration or a well‑indexed adjacency list with recursive queries may be better.

Ultimately, evaluate the trade‑offs of query speed, write complexity, storage overhead, and referential integrity to select the most suitable hierarchical data model for your project.