Nested Sets vs Adjacency Lists

Choose between recursive indexing strategies based on read-heavy or write-heavy requirements.

In this lesson, you will learn how to choose between Adjacency Lists and Nested Sets based on whether your application prioritizes frequent data modifications or intensive tree traversal.

When representing hierarchical data—like an organizational chart or product categories—the structure you choose dictates your indexing and query performance.

The Adjacency List: The Write-Friendly Approach

In an Adjacency List, each row simply stores a reference to its parent_id.

CREATE TABLE Categories (
    id INT PRIMARY KEY,
    name VARCHAR(50),
    parent_id INT,
    INDEX(parent_id) -- Crucial for navigating down
);

This is highly efficient for write-heavy workloads. Adding a node or moving a branch requires changing only one row’s parent_id. However, retrieving an entire subtree is computationally expensive. Because standard SQL struggle with arbitrary recursion, you often need to perform multiple round-trips to the database or use recursive Common Table Expressions (CTEs), which can become a bottleneck during heavy read traffic.

The Nested Set: The Read-Optimized Approach

Nested Sets represent hierarchies by assigning each node lft (left) and rgt (right) values. A node’s descendants are always found between its lft and rgt values.

SELECT * FROM Categories 
WHERE lft BETWEEN 1 AND 10;

This model is incredibly fast for read-heavy workloads. You can fetch entire subtrees or determine the depth of a node with a single, simple SELECT statement that utilizes a standard B-Tree index on the lft column.

The trade-off is the cost of writes. Inserting a new node into a Nested Set often requires shifting the lft and rgt values of many existing rows to "make space" in the sequence. This triggers extensive index updates and potential page splits, which can cause significant latch contention on your index pages if your tree is large or changes frequently.

Choosing Your Strategy

Choose Adjacency Lists if your hierarchy changes constantly (e.g., a real-time forum thread) and simple lookups suffice.
Choose Nested Sets if your data is relatively static and your application performs complex analytical queries or deep-tree traversals that would otherwise overwhelm the database with recursive scans.

Key Takeaway: Adjacency Lists offer superior write performance by localizing changes, whereas Nested Sets trade off write efficiency for lightning-fast subtree retrieval through range-based indexing.