Trees structures can be hard to represent and store in relational databases such as SQL Server.
Consider the table below:
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:
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):
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:
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:
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:
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.