Tree structure in SQL Server

Tree structures are a common data model used in many applications to represent hierarchical relationships between elements. In SQL Server, there are several ways to implement a tree structure, each with its own advantages and disadvantages. In this article, we will discuss the most common methods for storing and querying tree structures in SQL Server: Adjacency List, Nested Sets, Materialized Path, and Closure Table.

Adjacency List

The Adjacency List method involves creating a table with a parent-child relationship, where each node in the tree has a reference to its parent. The root node has a null parent reference. The following is an example of a table using the Adjacency List method:

CREATE TABLE TreeNode 
(
ID INT PRIMARY KEY, 
ParentID INT NULL, 
Data VARCHAR(255) 
);

• ID is the primary key of the table and the unique identifier of each node in the tree.
• ParentID is a foreign key that references the ID of the parent node. The root node will have a NULL value for this field.
• Data is a field that can be used to store any relevant data for the node.

To insert data into the table, you can use the following SQL statement:

INSERT INTO TreeNode (ID, ParentID, Data) 
VALUES (1, NULL, 'Root Node'), (2, 1, 'Child Node 1'), (3, 1, 'Child Node 2');

You can then use the following SQL statement to get all the children of a node:

SELECT * FROM TreeNode WHERE ParentID = 1;

Advantages:

• easy to understand and implement
• good for small and simple tree structures

Disadvantages:

• performs poorly for large and deep trees
• difficult to perform certain operations, such as moving a subtree from one location to another

Nested Sets

The Nested Sets method involves assigning a left and right value to each node in the tree, where the left value represents the start of the subtree and the right value represents the end of the subtree. This allows for easy traversal and querying of the tree, as well as efficient updates. The following is an example of a table using the Nested Sets method:

CREATE TABLE TreeNode 
(
ID INT PRIMARY KEY, 
Left INT NOT NULL, 
Right INT NOT NULL, 
Data VARCHAR(255) 
);

• ID is the primary key of the table and the unique identifier of each node in the tree.
• Left and Right are the values used to represent the start and end of the subtree.
• Data is a field that can be used to store any relevant data for the node.

Advantages:

• efficient for querying and updating large and deep trees
• easy to perform certain operations, such as moving a subtree from one location to another

Disadvantages:

• more complex to implement and understand
• less flexible for certain types of tree structures

Materialized Path

The Materialized Path method involves storing the path from the root to each node in the tree as a string, with each node represented by its primary key and separated by a delimiter. This allows for easy querying of the tree, but can be less efficient for updates. The following is an example of a table using the Materialized Path.

Originally published at https://bogdanhatis.com on January 15, 2023.