How to represent a tree structure numerically in SQL Server

A 3 minute read written by Pandora October 15, 2015

A number tree

Trees structures can be hard to represent and store in relational databases such as SQL Server.

Consider the table below:

ID/Name Parent ID
1 NULL
2 1
3 1
4 2
5 4

Each record in the table represents a node. From the table above, we have five nodes: 1, 2, 3, 4, and 5. Node 1 is the root node since it has no parent ID. Nodes 2 and 3 are both the children of node 1. Node 4 is the child of node 2. Node 5 is the child of node 4.

Visually, the tree looks like this:

a number tree

As you can see, it is difficult to visually view the path to a node just by looking at the table above. As well, retrieving the entire tree or finding all children of a node each time is recursive and expensive.

Here is a simple method that is easy to understand and displays the full hierarchy very quickly and easily using SQL (we assume there is only one path to a node and there are no circular paths in the tree).

For the numerical mapping, we want to represent it as follows:

  • The root page will have an ID of 0.0.
  • Each child page from the root page will have an ID of 1, 2, etc. from left to right.
  • Each of those child pages will have children that will each have ID of 1.1, 1.2, etc. from left to right.

Visually, the tree’s numerical mapping will look like so (written beside each node):

a number tree with numerical mapping

Here is the table definition for the tree:

CREATE TABLE tree(
	id int NOT NULL,
	parentid int NULL,
	name nvarchar(300) NOT NULL,
	depth int NULL,
	pathindex int NULL,
	numericalmapping nvarchar(300) NULL
)

Create a table like so:

ID/Name Parent ID Depth PathIndex NumericalMapping
1 NULL NULL NULL NULL
2 1 NULL NULL NULL
3 1 NULL NULL NULL
4 2 NULL NULL NULL
5 4 NULL NULL NULL

Run the following queries:

//First, set depth to 0 for root node
UPDATE tree SET depth = 0 
WHERE parentId IS NULL;
//Calculate depth for each node in tree by putting a loop to run through all nodes of the tree
WHILE EXISTS (SELECT * FROM tree WHERE depth IS NULL) 
	UPDATE T SET T.depth = P.depth + 1
		FROM tree AS T INNER JOIN tree AS P 
        ON (T.parentId = P.Id) 
    WHERE P.depth >= 0 
    AND T.depth IS NULL;
//Set path index and numerical mapping for root node
UPDATE tree SET pathindex = 0, numericalMapping = '0.0'
WHERE parentId IS NULL;
//Calculate path index and set it for each node (except for the root node)
;WITH x AS 
(
    SELECT id, rank() over (partition by parentId order by id) as pathindex 
    FROM tree 
    WHERE parentId IS NOT NULL  
)
UPDATE tree 
SET pathindex = x.pathindex
FROM x 
WHERE tree.id = x.id;
//Set the numerical mapping to the path index for children nodes that have depth of 1
UPDATE tree
SET numericalmapping = pathindex 
WHERE depth = 1;
//Calculate numerical mapping for nodes (except for the root node)
WHILE EXISTS (SELECT * FROM tree WHERE numericalMapping Is Null) 
    UPDATE T SET T.numericalMapping =   cast(P.numericalmapping as 
                                            varchar(300)) + '.' + 
                                        cast(T.pathindex as varchar(300))  
		FROM tree AS T INNER JOIN tree AS P 
		ON (T.parentId = P.Id) 
    WHERE P.pathindex >= 0 
    AND T.numericalMapping IS NULL;  

The tree table will now look like this:

ID/Name Parent ID Depth PathIndex NumericalMapping
1 NULL 0 0 0.0
2 1 1 1 1
3 1 1 2 2
4 2 2 1 1.1
5 4 3 1 1.1.1

To order the numerical mapping by depth first, simply run the following query:

WITH Items(id, parentid, name, depth, pathindex, ItemNumber) 
AS 
(
	SELECT id, parentid, name, depth, pathindex, numericalmapping
	FROM octave_uat.dbo.tree
) 
SELECT * 
FROM Items 
ORDER BY CONVERT(hierarchyid, '/' + ItemNumber + '/')

The sorted result will be the following:

ID/Name Parent ID Depth PathIndex NumericalMapping
1 NULL 0 0 0.0
2 1 1 1 1
4 2 2 1 1.1
5 4 3 1 1.1.1
3 1 1 2 2

With the depth and numerical mappings now calculated and saved in the table, we can quickly and easily view the path of a node and its depth. Only a simple select query is needed each time we need to retrieve the entire tree.

Now you know an easy way to represent a tree structure numerically in SQL Server. If you have other tips, please share them in the comments.