Given a parent-child relationship in a database table (hierarchical/tree data structure), most methods require multiple table scans to draw the hierarchical/tree data on the client-side. The method I have invented in 2002 can do the same in one table scan.
Please Note
There are a lot of changes to the article. So please reread the article if you have done so before.
All SQL statement examples are Microsoft SQL Server specific. The choice of delimiters/separators ('.' character) is to do with default English sort (Order by) collation of a Microsoft SQL Server installation. The example used in this article is for demonstration purposes only. I have tested the sample on:
- Microsoft SQL Server 2019 version 15.0.4033.1
- Language: English (United States)
- Collation: SQL_Latin1_General_CP1_CI_AS)
- Microsoft SQL Server Management Studio (SSMS) version 15.0.18330.0
Look at the end of the article for SQL query script to create the database, create the table and populate it with the exact order of data in the example I have used in this article.
Warning (Suggested; When To Use)
People in the comments (shout out to C. Grant Anderson) have been saying many useful statements.
I would like to suggest that you only use this algorithm when you want to fetch very large amounts of data and with a deep tree structure (meaning many levels/branches and sub-branches). This, I thought, was obvious but now from the comments, I realise I need to clarify it. The whole point is fetching a very large amount of tree data from the RDBMS (Relational Database Management System a.k.a. database with flat tables) and presenting it super fast to the user (UI; User Interface).
For normal amounts of data, this technique is overkill and not useful. This is not meant as a blind replacement to any of the existing techniques but just another technique to choose.
In agreement with the flames about why you would need to display millions of nodes of data to a user, it should not be required. However, I present to you another use case. Suppose you had a bunch of class objects that need to be filled with the nodes and data in the hierarchy tree structure quickly and fed to an Artificial Intelligence or some other algorithm that would do something with the data but needed it to be in a hierarchical/tree format, then this technique would come in handy. Again, I will say this as a possibility maybe a use case that is valid. I will field comment-based discussion on this use case idea of where this technique would be potentially useful.
History of Algorithm
When I was at T.C.S. (TATA Consultancy Services) in Mumbai, India in 2002, I was setting up a Linux C.O.E. (Center of Excellence) for G.E. (General Electric) account. This position was non-billable. The purpose was to create a delivery capability for Linux within this customer account. One challenge I faced was that coming up with Linux capability required a document management software to be purchased to store the documents in an easily accessible manner. A document management system would help to create, keep and disseminate knowledge to other people to learn how to deliver and execute Linux based projects. However, since I had no budget, I could not purchase any document management software. So with free A.S.P., Notepad, IIS Express, SQL Server Express and Gimp, I created a document management website to hold documents. The first system I created was simple. The parent folders or categories and documents are shown on the home page. Clicking on a folder or category name or document opened it up in the next page. This was horrible and slow. So I racked my brains for a couple of months on how to do it better. Finally, I came up with this algorithm which was 1.10.8 based. Wrote the horrible A.S.P. ultra-complicated code in Notepad (no budget for Visual Studio license) built the functional document management website. All the other C.O.E.s started using my website too as they liked it and all needed a Document Management system which they had no budget to purchase.
Note - Under India law 2002 software algorithms are not patentable. Only software solutions that are linked/tied/dependent on some hardware as a whole (software+hardware) system are patentable. So this invention of mine cannot be owned by T.C.S. or myself, the person who invented it. This note is there for those who are worried about ownership of this algorithm I have created.
Introduction
A simple table in a relational database is the Employees table. It has an employee I.D., and a Reports to I.D. which is an employee I.D. The standard way to fill your tree with this hierarchical information is to query for the root nodes, i.e., nodes with no parents; in this case, null in Reports to. Then, subsequently, query the table for all children of the node, i.e., Reports to I.D. equals the root employee I.D. Keep doing this until you come to leaf nodes with empty results. I will describe a better technique that avoids repetitive queries.
How to Represent the Data in the Relational Database Side
One part of the technique is to create a new key column in your relational table, which has the hierarchical information in it. An example is as below:
Table Name: TreeTable.
| Node ID (int identity) | Parent ID (int) | My Key (nvarchar[max]) | Data (nvarchar[max]) |
1 | <code>NULL | A | Akshay Srinivasan |
2 | <code>NULL | B | Douglas Mitchell |
3 | 1 | A.A | George Yates |
4 | 2 | B.A | Dan Brown |
5 | 3 | A.A.A | Chris Jones |
6 | 4 | B.A.A | Matt Daniels |
7 | 1 | A.B | Andrew Brown |
8 | 3 | A.A.B | Timothy Cook |
9 | 3 | A.A.C | Jane Franklin |
10 | 1 | A.C | Zachary Cage |
11 | 3 | A.A.D | Nancy Carter |
12 | 1 | A.D | Bill Smith |
13 | 3 | A.A.E | Frank Richards |
As you can see from this example, random inserts are going on, so the Data is out of order. However, with a basic query that orders by the [My Key] column, this Data will be in hierarchical sequence. An example follows:
select * from TreeTable order by [My Key]
The result of this SQL query is the following:
| Node ID | Parent ID | My Key | Data |
1 | NULL | A | Akshay Srinivasan |
3 | 1 | A.A | George Yates |
5 | 3 | A.A.A | Chris Jones |
8 | 3 | A.A.B | Timothy Cook |
9 | 3 | A.A.C | Jane Franklin |
11 | 3 | A.A.D | Nancy Carter |
13 | 3 | A.A.E | Frank Richards |
7 | 1 | A.B | Andrew Brown |
10 | 1 | A.C | Zachary Cage |
12 | 1 | A.D | Bill Smith |
2 | NULL | B | Douglas Mitchell |
4 | 2 | B.A | Dan Brown |
6 | 4 | B.A.A | Matt Daniels |
The symbology is not pertinent here. The values in the [My Key] column just requires that you use symbols for the nodes that are unique at the level of the tree that it exists at, and these symbols should sort in order according to the sort order of the database. It means that when you insert into a level, you should use the next available symbol, which in this case is the next alphabetical character. The delimiter again could be any symbol; I have chosen '.' for convenience. The key at any level combines the key of the parent before it, as can readily be seen. Now the advantage is this puts almost no load on any existing relational database as it exists today, as sorting is very basic and all database systems have implemented the "Order by" with great efficiency. The next step is how the client processes this information.
When coming to the end of the symbol range in this case alphabet Z, you would append to Z the next series of symbols in this case alphabet A which would result in Z.A. Coming to the end of this range, you would go Z.Z.A. as next series.
An important point when choosing the delimiter/separator, in this simple example the '.' character, you need to make sure that the '.' character is ordered before any of the symbols in the symbol range. In this case '.' sorts before the symbol range of characters A through Z.
Note: The [Node ID] and [Parent ID] columns are only there to give you a chance to see how the old concept compares to the new concept in the [My Key] column introduce by my algorithm. Why is this the case? The symbols after the last delimiter/separator in the [My Key] column value is equivalent to the [Node ID]. The rest of the symbols and delimiters/separators before the last delimiter/separator in the [My Key] column value is equivalent to the [Parent ID] column. If you do get rid of [Node ID] and [Parent ID] optional columns you will have to change the SQL queries.
Client Processing
The client merely recurses over each row, checking to see if the [My Key] column value in the current row starts with the [My Key] column value from the previous row. If it does, it recurses to fill the tree at the next level. If it does not, it falls back down to the level below and checks for a match until it lands up at the root node level and adds it as a root node. It is a straightforward algorithm for the client. And, in fractions of a second, you can fill a treeview or any other type of hierarchical visual control, or also any data structure that you might want to fill. Let's talk about inserting data into this tree or updating it. All you need to do on an insert is check what the [My Key] column value of the parent node is and append it to the beginning of the [My Key] value of the node you are inserting into the table, and append a unique identifier that has not been used before at this level of the tree. In my example case, it would be the next highest alphabetical character. It could just be the identity value of the current record you are inserting. As simple as that, which is always unique and implemented by a database like SQL Server. Or a sequence in Oracle. An update will change the [My Key] column value from the old parent node [My Key] column value to the new node's [My Key] column value. For the case in which you want to use the new Identity/Sequence value to append to the new [My Key] column value of a node, you can also use an algorithm to transform the integer into a character symbol from your chose character symbol range.
Summary
This technique allows you to efficiently present hierarchical data from a flat relational table with just one query to the relational database instead of multiple queries. It is much faster than existing techniques, and you should employ it wherever you have a relational table with hierarchical information in it.
Where Do I Use It?
When I invented this technique in 2002, I was working with a huge tree that had unlimited growth potential for which the existing methods that I knew of did not stand up to. An example of where this would be useful is for the parts explosion of an aircraft, the employee table that holds organizational chart information for a Fortune 500 company or one with many employees, or a scientific work which involves huge trees. It is useful with small trees when you wish to display the tree in its entirety in one shot very quickly. I have shown how to insert, update, delete, and move branches so that you can use the system out of the box. But these are merely there for support, and not the reason to use the technique. This should answer the question, "Where do I use it?"
How to Select
To select the basic information is very simple and an example is given below:
select * from TreeTable order by [My Key]
"TreeTable" being the name of the table from now on and [My Key] being the name of the column containing the key like "ZZH.JA.ZZZD" for example.
If you want to select all nodes under a particular parent node. In this example, all nodes under the parent [My Key] column with value 'A' then:
select * from TreeTable where [My Key] like 'A' + '.%' order by [My Key]
If you want to select children of a node without bringing all the nodes under the child nodes. The following SQL query example does this for all the child nodes of the 'A.A.' node:
select [My Key] from TreeTable where [My Key] like 'A.A' + '.%' and
(len('A.A') - len(replace('A.A', '.', ''))) + 1 = (len([My Key]) -
len(replace([My Key], '.', '')))
What this is essentially doing is counting the delimiters/separators and seeing if the chosen parent node, which in this example is 'A.A.', count of the delimiter/separator ('.' character), which in this example is 1, is equal to the count of delimiter/separator in the child nodes. So given 'A.A.' as the supplied parent nodes [My Key] column value the number of '.' characters is 1. Its immediate children have to start with 'A.A.' and should not have another '.' character in them which would denote a further sub-level. So the immediate children can only have a '.' character count in their [My Key] column value of 2. The following is the result of the SQL query:
| Node ID (int identity) | Parent ID (int) | My Key (nvarchar[max]) | Data (nvarchar[max]) |
5 | 3 | A.A.A | Chris Jones |
8 | 3 | A.A.B | Timothy Cook |
9 | 3 | A.A.C | Jane Franklin |
11 | 3 | A.A.D | Nancy Carter |
13 | 3 | A.A.E | Frank Richards |
How to Order the Tree Nodes by Some Other Column
So you have inserted data and keys into the table, and you want to order within a level alphabetically by some other data column or numerically, etc. This is a non-trivial task. So there are multiple approaches. The easiest one is you use the select order by technique to get the data out to code side. Then you sort within a [My Key] level in code and fill your treeview control. You can also query the old way which is inefficient but works for each level and sort within that node level all the children by the data column(s). To do this, use the following query:
select * from TreeTable order by
replace(iif(charindex('.', reverse([My Key]), 1) > 0,
substring([My Key], 1, len([My Key]) - charindex('.',
reverse([My Key]), 1) + 1), [My Key] + '@'), '.', '~'),
Data
TreeTable being the name of the table from now on and [My Key] being the name of the column containing the key like ZZH.JA.ZZZD for. Data being the column holding in my example alphabetic data a simple list of names. So what this does is search for the last '.' delimiter symbol and cut it off from the [My Key] value giving just the parent node this is then sorted by Data. So effectively within a node, all the node's children are ordered or sorted alphabetically. To sort the nodes the '.' delimiter or symbol is replaced with '~' delimiter or symbol. This is because I have chosen the capital case alphabet for my symbol set and it is default English collation so '~' will sort or order after A-Z. For root nodes which have no '.' symbol, the '@' symbol is used because it sorts or orders before A-Z and ~. The following is the result of the SQL query:
| Node ID (int identity) | Parent ID (int) | My Key (nvarchar[max]) | Data (nvarchar[max]) |
1 | NULL | A | Akshay Srinivasan |
7 | 1 | A.B | Andrew Brown |
9 | 1 | A.D | Bill Smith |
3 | 1 | A.A | George Yates |
8 | 1 | A.C | Zachary Cage |
5 | 3 | A.A.A | Chris Jones |
13 | 3 | A.A.E | Frank Richards |
11 | 3 | A.A.C | Jane Franklin |
12 | 3 | A.A.D | Nancy Carter |
10 | 3 | A.A.B | Timothy Cook |
2 | NULL | B | Douglas Mitchell |
4 | 2 | B.A | Dan Brown |
6 | 4 | B.A.A | Matt Daniels |
To sort, of course, the children of a single node the SQL becomes much simpler:
select * from TreeTable where [My Key] like 'A.%' order by
replace(iif(charindex('.', reverse([My Key]), 1) > 0,
substring([My Key], 1, len([My Key]) - charindex('.',
reverse([My Key]), 1) + 1), [My Key] + '@'), '.', '~'),
Data
Essentially, you have the parent nodes [My Key] and you want to sort the tree nodes under it properly so the addition is the "like" Transact-SQL keyword that will pick up all the children. The result of the SQL query is:
| Node ID (int identity) | Parent ID (int) | My Key (nvarchar[max]) | Data (nvarchar[max]) |
7 | 1 | A.B | Andrew Brown |
9 | 1 | A.D | Bill Smith |
3 | 1 | A.A | George Yates |
8 | 1 | A.C | Zachary Cage |
5 | 3 | A.A.A | Chris Jones |
13 | 3 | A.A.E | Frank Richards |
11 | 3 | A.A.C | Jane Franklin |
12 | 3 | A.A.D | Nancy Carter |
10 | 3 | A.A.B | Timothy Cook |
How to Create a New Root or Child Node
When adding a new root node, you need to find out what is the last root node that was inserted. You then increment the last character of the last root node created to the next symbol in the symbol range. In this example, it is 'A' through 'Z'. So say in the example, the last node is 'B'. So the next node would be 'C'.
If there is a delimiter/separator ('.' in the example) in the [My Key] column value of the parent node then we need to find out which immediate child node is the last node. Once we find this [My Key] column value increment the last character to the next symbol in the symbol range. In this example, it is 'A' through 'Z'. So say in the example, the last node is 'A.A.E.' then the next node would be 'A.A.F.'. If the last node is 'A.A. Z' then the next node is 'A.A.ZA'.
The following stored procedure implements creation (insert) of a new record in the table. This stored procedure accepts the [My Key] column value of the parent node you are trying to create a new node for using the parameter 'ParentMyKeyValue'. If this parameter is a null or empty string ('') then it will check and create a new root node. If this parameter has a value then it will append a new node to the parent node whose [My Key] column value equals this parameter's value. The second parameter, 'ChildNodeToCreatesDataValue', is simply data for the example which is a nvarchar(max) which is simply a Unicode string. The third parameter, 'FirstCharInSymbolRange', is the start of the symbol range used to define [My Key] column values. In the example, that would be 'A'. The fourth parameter, 'LastCharInSymbolRange', is the end of the symbol range. In the example that would be 'Z'. The fifth parameter, 'DelimiterOrSeparatorValue', is the delimiter/separator used to define [My Key] column values. In the example, that would be '.'.
create procedure uspInsertChildNodeGivenParentNodeMyKey
(
@ParentMyKeyValue nvarchar(max),
@ChildNodeToCreatesDataValue nvarchar(max),
@FirstCharInSymbolRange nvarchar(1),
@LastCharInSymbolRange nvarchar(1),
@DelimiterOrSeparatorValue nvarchar(1)
)
as
begin
declare @IntValueOfLastCharInSymbolRange int;
declare @ParentNodeIDValue int;
declare @LastImmediateChildNodesMyKey nvarchar(max);
declare @IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey int;
declare @NewMyKeyValueForNewChildNode nvarchar(max);
declare @LastRootNodeMyKeyValue nvarchar(max);
declare @IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue int;
declare @NewMyKeyValueForNewRootNode nvarchar(max);
set @IntValueOfLastCharInSymbolRange = unicode(@LastCharInSymbolRange)
select @ParentNodeIDValue = [Node ID] from TreeTable where [My Key] = @ParentMyKeyValue
if (@ParentMyKeyValue is null or len(@ParentMyKeyValue) = 0) or
(@ParentMyKeyValue is not null and len(@ParentMyKeyValue) > 0 and
exists (select [My Key] from TreeTable where [My Key] = @ParentMyKeyValue))
begin
if @ParentMyKeyValue is null or len(@ParentMyKeyValue) = 0
begin
select top 1 @LastRootNodeMyKeyValue = [My Key]
from TreeTable where
[Parent ID] is null
order by [My Key] desc;
if @LastRootNodeMyKeyValue is not null and len(@LastRootNodeMyKeyValue) > 0
begin
set @IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue =
unicode(substring(reverse(@LastRootNodeMyKeyValue), 1, 1));
if @IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue =
@IntValueOfLastCharInSymbolRange
begin
insert into TreeTable ([Parent ID], [My Key], [Data])
values (NULL, substring(@LastRootNodeMyKeyValue, 1,
len(@LastRootNodeMyKeyValue) - 1) + @LastCharInSymbolRange +
@FirstCharInSymbolRange, @ChildNodeToCreatesDataValue);
end
else
begin
insert into TreeTable ([Parent ID], [My Key], [Data])
values (NULL, substring(@LastRootNodeMyKeyValue, 1,
len(@LastRootNodeMyKeyValue) - 1) +
nchar(@IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue + 1),
@ChildNodeToCreatesDataValue);
end
end
else
begin
insert into TreeTable ([Parent ID], [My Key], [Data])
values (NULL, @FirstCharInSymbolRange, @ChildNodeToCreatesDataValue);
end
end
else
begin
select top 1 @LastImmediateChildNodesMyKey = [My Key]
from TreeTable where
[My Key] like @ParentMyKeyValue + @DelimiterOrSeparatorValue + '%' and
(len(@ParentMyKeyValue) - len(replace(@ParentMyKeyValue,
@DelimiterOrSeparatorValue, ''))) + 1 =
(len([My Key]) - len(replace([My Key], @DelimiterOrSeparatorValue, '')))
order by [My Key] desc;
if @LastImmediateChildNodesMyKey is not null _
and len(@LastImmediateChildNodesMyKey) > 0
begin
set @IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey =
unicode(substring(reverse(@LastImmediateChildNodesMyKey), 1, 1))
if @IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey =
@IntValueOfLastCharInSymbolRange
begin
set @NewMyKeyValueForNewChildNode = @LastImmediateChildNodesMyKey +
@FirstCharInSymbolRange
end
else
begin
set @NewMyKeyValueForNewChildNode = _
substring(@LastImmediateChildNodesMyKey, 1,
len(@LastImmediateChildNodesMyKey) - 1) +
nchar(@IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey + 1)
end
end
else
begin
set @NewMyKeyValueForNewChildNode = _
@ParentMyKeyValue + @DelimiterOrSeparatorValue +
@FirstCharInSymbolRange
end
insert into TreeTable ([Parent ID], [My Key], [Data])
values (@ParentNodeIDValue, _
@NewMyKeyValueForNewChildNode, @ChildNodeToCreatesDataValue)
end
end
end
GO
To demonstrate the stored procedure in action to create a root node. A node with no parent node. Try the following SQL query:
exec uspInsertChildNodeGivenParentNodeMyKey @ParentMyKeyValue = null,
@ChildNodeToCreatesDataValue = 'Johnathon Swift',
@FirstCharInSymbolRange = 'A',
@LastCharInSymbolRange ='Z',
@DelimiterOrSeparatorValue = '.'
GO
Now you should see a new root node with [My Key] column value as 'C' and with its data column value set to 'Johnathon Swift'.
To demonstrate the stored procedure in action to create a child node of a supplied parent node [My Key] column value. Try the following SQL query:
exec uspInsertChildNodeGivenParentNodeMyKey @ParentMyKeyValue = 'A.A',
@ChildNodeToCreatesDataValue = 'Chantal Jeffreys',
@FirstCharInSymbolRange = 'A',
@LastCharInSymbolRange ='Z',
@DelimiterOrSeparatorValue = '.'
GO
Now you should see a new child node of the node with [My Key] column value of 'A.A.'. The new child nodes [My Key] column value would be 'A.A.F.'. This is because the last child had a [My Key] column value of 'A.A.E.'. The data column value is of course set to the supplied value of 'Chantal Jeffreys'.
How to Delete a Node
Deleting one node only is trivial you just delete the node for the key. You should never delete a node without deleting its child nodes as orphaned nodes will break the drawing algorithm. To delete a node and all its child nodes then you would use the following statement to delete for example all child nodes of the node with [My Key] column value of 'A.A.':
delete from TreeTable where [My Key] like 'A.A.%' or [My Key] = 'A.A'
This will delete the 'A.A.' node and all nodes in the branches below this node.
Changing the Parent Node of a Node
To update or move a node to become a child node of another existing node, you would have to do the following logical steps in order:
- Check if the node you are trying to move to is a child of the node that is being moved. If it is a child node, then do not move the node.
- Find the
[My Key] column value of the parent node of the node you want to move. If it is a root node, then its [My Key] value is null or empty and can be ignored. - Find the next symbol value from the existing child nodes, if any, of the new parent node.
- Now take the new parent node
[My Key] column value and append the next symbol found in step 2. This will be the new [My Key] column value of the node that is being moved to the new parent node. - Replace the old parent node
[My Key] column value from step 1 with the new [My Key] column value from step 3. Do this for the node being moved and all its children.
The following is the stored procedure for moving a node and all its children to another target node:
create procedure uspMoveNodeAlongWithItsChildrenUnderANewTargetNode
(
@MyKeyValueOfNodeToBeMoved nvarchar(max),
@MyKeyValueOfNodeToMoveTo nvarchar(max),
@FirstCharInSymbolRange nvarchar(1),
@LastCharInSymbolRange nvarchar(1),
@DelimiterOrSeparatorValue nvarchar(1)
)
as
begin
declare @NodeToBeMovedTosLastImmediateChildMyKeyValue nvarchar(max)
declare @ParentIDOfNodeToMoveTo int
declare @NewMyKey nvarchar(max)
declare @IntValueOfLastCharInSymbolRange int
declare @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart int
set @IntValueOfLastCharInSymbolRange = unicode(@LastCharInSymbolRange);
select @ParentIDOfNodeToMoveTo = [Node ID] from TreeTable where
[My Key] = @MyKeyValueOfNodeToMoveTo;
if iif(@MyKeyValueOfNodeToBeMoved is not null and len(@MyKeyValueOfNodeToBeMoved) > 0 and
exists (select [My Key] from TreeTable where [My Key] = @MyKeyValueOfNodeToBeMoved),
iif(charindex(@MyKeyValueOfNodeToBeMoved, @MyKeyValueOfNodeToMoveTo) <> 1, iif(
(@MyKeyValueOfNodeToMoveTo is null or len(@MyKeyValueOfNodeToMoveTo) = 0) or (
@MyKeyValueOfNodeToMoveTo is not null and len(@MyKeyValueOfNodeToMoveTo) > 0 and
exists (select [My Key] from TreeTable where [My Key] = @MyKeyValueOfNodeToMoveTo)),
'Enter', 'Exit'), 'Exit'), 'Exit') = 'Enter'
begin
if @MyKeyValueOfNodeToMoveTo is null or len(@MyKeyValueOfNodeToMoveTo) = 0
begin
select top 1 @NodeToBeMovedTosLastImmediateChildMyKeyValue = [My Key] _
from TreeTable where
charindex(@DelimiterOrSeparatorValue, [My Key]) = 0 order by [My Key] desc;
set @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart =
unicode(substring_
(reverse(@NodeToBeMovedTosLastImmediateChildMyKeyValue), 1, 1));
if @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart = _
@IntValueOfLastCharInSymbolRange
begin
update TreeTable set [Parent ID] = null, [My Key] =
@NodeToBeMovedTosLastImmediateChildMyKeyValue + _
@FirstCharInSymbolRange where
[My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @NodeToBeMovedTosLastImmediateChildMyKeyValue +
@FirstCharInSymbolRange + @DelimiterOrSeparatorValue + substring([My Key],
len(@MyKeyValueOfNodeToBeMoved) + 2, len([My Key]) -
len(@MyKeyValueOfNodeToBeMoved) - 1) where [My Key] like
@MyKeyValueOfNodeToBeMoved + @DelimiterOrSeparatorValue + '%';
end
else
begin
set @NewMyKey = substring(@NodeToBeMovedTosLastImmediateChildMyKeyValue, 1,
len(@NodeToBeMovedTosLastImmediateChildMyKeyValue) - 1) +
nchar(@IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart + 1);
update TreeTable set [Parent ID] = null,
[My Key] = @NewMyKey where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @NewMyKey + _
@DelimiterOrSeparatorValue + substring([My Key],
len(@MyKeyValueOfNodeToBeMoved) + 2, _
len([My Key]) - len(@MyKeyValueOfNodeToBeMoved) - 1)
where [My Key] like @MyKeyValueOfNodeToBeMoved + _
@DelimiterOrSeparatorValue + '%';
end
end
else
begin
select top 1 @NodeToBeMovedTosLastImmediateChildMyKeyValue = _
[My Key] from TreeTable where
[My Key] like @MyKeyValueOfNodeToMoveTo + @DelimiterOrSeparatorValue + '%' and
(len(@MyKeyValueOfNodeToMoveTo) - len(replace(@MyKeyValueOfNodeToMoveTo,
@DelimiterOrSeparatorValue, ''))) + 1 =
(len([My Key]) - len(replace([My Key], @DelimiterOrSeparatorValue, '')))
order by [My Key] desc;
if @NodeToBeMovedTosLastImmediateChildMyKeyValue is null or
len(@NodeToBeMovedTosLastImmediateChildMyKeyValue) = 0
begin
update TreeTable set [Parent ID] = @ParentIDOfNodeToMoveTo,
[My Key] = @MyKeyValueOfNodeToMoveTo + @DelimiterOrSeparatorValue +
@FirstCharInSymbolRange where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @MyKeyValueOfNodeToMoveTo + _
@DelimiterOrSeparatorValue
+ @FirstCharInSymbolRange + @DelimiterOrSeparatorValue + substring([My Key],
len(@MyKeyValueOfNodeToBeMoved) + 2, _
len([My Key]) - len(@MyKeyValueOfNodeToBeMoved)
- 1) where [My Key] like @MyKeyValueOfNodeToBeMoved + _
@DelimiterOrSeparatorValue + '%';
end
else
begin
set @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart =
unicode(substring(reverse_
(@NodeToBeMovedTosLastImmediateChildMyKeyValue), 1, 1));
if @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart = _
@IntValueOfLastCharInSymbolRange
begin
set @NewMyKey = @NodeToBeMovedTosLastImmediateChildMyKeyValue + _
@FirstCharInSymbolRange;
update TreeTable set [Parent ID] = @ParentIDOfNodeToMoveTo, [My Key] =
@NewMyKey where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @NewMyKey + @DelimiterOrSeparatorValue +
substring([My Key], len(@MyKeyValueOfNodeToBeMoved) + 2,
len([My Key]) -
len(@MyKeyValueOfNodeToBeMoved) - 1) where
[My Key] like @MyKeyValueOfNodeToBeMoved + _
@DelimiterOrSeparatorValue + '%';
end
else
begin
set @NewMyKey =
substring(@NodeToBeMovedTosLastImmediateChildMyKeyValue, 1,_
len(@NodeToBeMovedTosLastImmediateChildMyKeyValue) - 1) + _
nchar(@IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart_
+ 1);
update TreeTable set [Parent ID] = @ParentIDOfNodeToMoveTo,
[My Key] = @NewMyKey where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @NewMyKey + @DelimiterOrSeparatorValue +
substring([My Key],
len(@MyKeyValueOfNodeToBeMoved) + 2, len([My Key]) -
len(@MyKeyValueOfNodeToBeMoved) - 1) where [My Key] like
@MyKeyValueOfNodeToBeMoved + @DelimiterOrSeparatorValue + '%';
end
end
end
end
end
GO
I will now move the root node with [My Key] column value of 'B' to the node with [My Key] column value of 'A.A'. I will also update all of the node's children [My Key] column value to reflect the change using the following SQL query:
exec uspMoveNodeAlongWithItsChildrenUnderANewTargetNode
@MyKeyValueOfNodeToBeMoved = 'B',
@MyKeyValueOfNodeToMoveTo = 'A.A',
@FirstCharInSymbolRange = 'A',
@LastCharInSymbolRange = 'Z',
@DelimiterOrSeparatorValue = '.'
GO
Microsoft SQL Server Script
The following Microsoft SQL Server script is for creating the database, creating the table, creating the stored procedure and populating with example data in the correct order of insertion as used in this article.
USE [master]
GO
IF (EXISTS (SELECT name
FROM master.dbo.sysdatabases
WHERE name = 'TreeDB'))
DROP DATABASE [TreeDB]
GO
CREATE DATABASE [TreeDB]
CONTAINMENT = NONE
ON PRIMARY
( NAME = N'TreeDB', _
FILENAME = N'D:\SQLServerUserDatabases\TreeDB.mdf' , SIZE = 8192KB , _
MAXSIZE = UNLIMITED, FILEGROWTH = 65536KB )
LOG ON
( NAME = N'TreeDB_log', _
FILENAME = N'D:\SQLServerUserDatabases\TreeDB_log.ldf' , SIZE = 8192KB , _
MAXSIZE = 2048GB , FILEGROWTH = 65536KB )
WITH CATALOG_COLLATION = DATABASE_DEFAULT
GO
IF (1 = FULLTEXTSERVICEPROPERTY('IsFullTextInstalled'))
begin
EXEC [TreeDB].[dbo].[sp_fulltext_database] @action = 'enable'
end
GO
ALTER DATABASE [TreeDB] SET ANSI_NULL_DEFAULT OFF
GO
ALTER DATABASE [TreeDB] SET ANSI_NULLS OFF
GO
ALTER DATABASE [TreeDB] SET ANSI_PADDING OFF
GO
ALTER DATABASE [TreeDB] SET ANSI_WARNINGS OFF
GO
ALTER DATABASE [TreeDB] SET ARITHABORT OFF
GO
ALTER DATABASE [TreeDB] SET AUTO_CLOSE OFF
GO
ALTER DATABASE [TreeDB] SET AUTO_SHRINK OFF
GO
ALTER DATABASE [TreeDB] SET AUTO_UPDATE_STATISTICS ON
GO
ALTER DATABASE [TreeDB] SET CURSOR_CLOSE_ON_COMMIT OFF
GO
ALTER DATABASE [TreeDB] SET CURSOR_DEFAULT GLOBAL
GO
ALTER DATABASE [TreeDB] SET CONCAT_NULL_YIELDS_NULL OFF
GO
ALTER DATABASE [TreeDB] SET NUMERIC_ROUNDABORT OFF
GO
ALTER DATABASE [TreeDB] SET QUOTED_IDENTIFIER OFF
GO
ALTER DATABASE [TreeDB] SET RECURSIVE_TRIGGERS OFF
GO
ALTER DATABASE [TreeDB] SET DISABLE_BROKER
GO
ALTER DATABASE [TreeDB] SET AUTO_UPDATE_STATISTICS_ASYNC OFF
GO
ALTER DATABASE [TreeDB] SET DATE_CORRELATION_OPTIMIZATION OFF
GO
ALTER DATABASE [TreeDB] SET TRUSTWORTHY OFF
GO
ALTER DATABASE [TreeDB] SET ALLOW_SNAPSHOT_ISOLATION OFF
GO
ALTER DATABASE [TreeDB] SET PARAMETERIZATION SIMPLE
GO
ALTER DATABASE [TreeDB] SET READ_COMMITTED_SNAPSHOT OFF
GO
ALTER DATABASE [TreeDB] SET HONOR_BROKER_PRIORITY OFF
GO
ALTER DATABASE [TreeDB] SET RECOVERY FULL
GO
ALTER DATABASE [TreeDB] SET MULTI_USER
GO
ALTER DATABASE [TreeDB] SET PAGE_VERIFY CHECKSUM
GO
ALTER DATABASE [TreeDB] SET DB_CHAINING OFF
GO
ALTER DATABASE [TreeDB] SET FILESTREAM( NON_TRANSACTED_ACCESS = OFF )
GO
ALTER DATABASE [TreeDB] SET TARGET_RECOVERY_TIME = 60 SECONDS
GO
ALTER DATABASE [TreeDB] SET DELAYED_DURABILITY = DISABLED
GO
ALTER DATABASE [TreeDB] SET QUERY_STORE = OFF
GO
ALTER DATABASE [TreeDB] SET READ_WRITE
GO
USE [TreeDB]
GO
IF EXISTS (SELECT * FROM sys.objects WHERE object_id = _
OBJECT_ID(N'[dbo].[TreeTable]') AND type in (N'U'))
DROP TABLE [dbo].[TreeTable]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[TreeTable](
[Node ID] [int] IDENTITY(1,1) NOT NULL,
[Parent ID] [int] NULL,
[My Key] [nvarchar](max) NOT NULL,
[Data] [nvarchar](max) NOT NULL
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
GO
IF EXISTS (SELECT * FROM sys.objects WHERE object_id = _
OBJECT_ID(N'[dbo].[uspInsertChildNodeGivenParentNodeMyKey]') AND type in (N'P'))
DROP PROCEDURE [dbo].[uspInsertChildNodeGivenParentNodeMyKey]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
create procedure uspInsertChildNodeGivenParentNodeMyKey
(
@ParentMyKeyValue nvarchar(max),
@ChildNodeToCreatesDataValue nvarchar(max),
@FirstCharInSymbolRange nvarchar(1),
@LastCharInSymbolRange nvarchar(1),
@DelimiterOrSeparatorValue nvarchar(1)
)
as
begin
declare @IntValueOfLastCharInSymbolRange int;
declare @ParentNodeIDValue int;
declare @LastImmediateChildNodesMyKey nvarchar(max);
declare @IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey int;
declare @NewMyKeyValueForNewChildNode nvarchar(max);
declare @LastRootNodeMyKeyValue nvarchar(max);
declare @IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue int;
declare @NewMyKeyValueForNewRootNode nvarchar(max);
set @IntValueOfLastCharInSymbolRange = unicode(@LastCharInSymbolRange)
select @ParentNodeIDValue = [Node ID] from TreeTable where [My Key] = @ParentMyKeyValue
if (@ParentMyKeyValue is null or len(@ParentMyKeyValue) = 0) or
(@ParentMyKeyValue is not null and len(@ParentMyKeyValue) > 0 and
exists (select [My Key] from TreeTable where [My Key] = @ParentMyKeyValue))
begin
if @ParentMyKeyValue is null or len(@ParentMyKeyValue) = 0
begin
select top 1 @LastRootNodeMyKeyValue = [My Key]
from TreeTable where
[Parent ID] is null
order by [My Key] desc;
if @LastRootNodeMyKeyValue is not null and len(@LastRootNodeMyKeyValue) > 0
begin
set @IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue =
unicode(substring(reverse(@LastRootNodeMyKeyValue), 1, 1));
if @IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue =
@IntValueOfLastCharInSymbolRange
begin
insert into TreeTable ([Parent ID], [My Key], [Data])
values (NULL, substring(@LastRootNodeMyKeyValue, 1,
len(@LastRootNodeMyKeyValue) - 1) + @LastCharInSymbolRange +
@FirstCharInSymbolRange, @ChildNodeToCreatesDataValue);
end
else
begin
insert into TreeTable ([Parent ID], [My Key], [Data])
values (NULL, substring(@LastRootNodeMyKeyValue, 1,
len(@LastRootNodeMyKeyValue) - 1) +
nchar(@IntValueOfLastCharacterOfEndOfLastRootNodeMyKeyValue + 1),
@ChildNodeToCreatesDataValue);
end
end
else
begin
insert into TreeTable ([Parent ID], [My Key], [Data])
values (NULL, @FirstCharInSymbolRange, @ChildNodeToCreatesDataValue);
end
end
else
begin
select top 1 @LastImmediateChildNodesMyKey = [My Key]
from TreeTable where
[My Key] like @ParentMyKeyValue + @DelimiterOrSeparatorValue + '%' and
(len(@ParentMyKeyValue) - len(replace(@ParentMyKeyValue,
@DelimiterOrSeparatorValue, ''))) + 1 =
(len([My Key]) - len(replace([My Key], @DelimiterOrSeparatorValue, '')))
order by [My Key] desc;
if @LastImmediateChildNodesMyKey is not null and _
len(@LastImmediateChildNodesMyKey) > 0
begin
set @IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey =
unicode(substring(reverse(@LastImmediateChildNodesMyKey), 1, 1))
if @IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey =
@IntValueOfLastCharInSymbolRange
begin
set @NewMyKeyValueForNewChildNode = @LastImmediateChildNodesMyKey +
@FirstCharInSymbolRange
end
else
begin
set @NewMyKeyValueForNewChildNode = _
substring(@LastImmediateChildNodesMyKey, 1, _
len(@LastImmediateChildNodesMyKey) - 1) + _
nchar(@IntValueOfLastCharacterOfEndOfLastImmediateChildNodesMyKey + 1)
end
end
else
begin
set @NewMyKeyValueForNewChildNode = _
@ParentMyKeyValue + @DelimiterOrSeparatorValue +
@FirstCharInSymbolRange
end
insert into TreeTable ([Parent ID], [My Key], [Data])
values (@ParentNodeIDValue, @NewMyKeyValueForNewChildNode, _
@ChildNodeToCreatesDataValue)
end
end
end
GO
IF EXISTS (SELECT * FROM sys.objects WHERE object_id = _
OBJECT_ID(N'[dbo].[uspMoveNodeAlongWithItsChildrenUnderANewTargetNode]') AND type in (N'P'))
DROP PROCEDURE [dbo].[uspMoveNodeAlongWithItsChildrenUnderANewTargetNode]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
create procedure uspMoveNodeAlongWithItsChildrenUnderANewTargetNode
(
@MyKeyValueOfNodeToBeMoved nvarchar(max),
@MyKeyValueOfNodeToMoveTo nvarchar(max),
@FirstCharInSymbolRange nvarchar(1),
@LastCharInSymbolRange nvarchar(1),
@DelimiterOrSeparatorValue nvarchar(1)
)
as
begin
declare @NodeToBeMovedTosLastImmediateChildMyKeyValue nvarchar(max)
declare @ParentIDOfNodeToMoveTo int
declare @NewMyKey nvarchar(max)
declare @IntValueOfLastCharInSymbolRange int
declare @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart int
set @IntValueOfLastCharInSymbolRange = unicode(@LastCharInSymbolRange);
select @ParentIDOfNodeToMoveTo = [Node ID] from TreeTable where
[My Key] = @MyKeyValueOfNodeToMoveTo;
if iif(@MyKeyValueOfNodeToBeMoved is not null and len(@MyKeyValueOfNodeToBeMoved) > 0 and
exists (select [My Key] from TreeTable where [My Key] = @MyKeyValueOfNodeToBeMoved),
iif(charindex(@MyKeyValueOfNodeToBeMoved, @MyKeyValueOfNodeToMoveTo) <> 1, iif(
(@MyKeyValueOfNodeToMoveTo is null or len(@MyKeyValueOfNodeToMoveTo) = 0) or (
@MyKeyValueOfNodeToMoveTo is not null and len(@MyKeyValueOfNodeToMoveTo) > 0 and
exists (select [My Key] from TreeTable where [My Key] = @MyKeyValueOfNodeToMoveTo)),
'Enter', 'Exit'), 'Exit'), 'Exit') = 'Enter'
begin
if @MyKeyValueOfNodeToMoveTo is null or len(@MyKeyValueOfNodeToMoveTo) = 0
begin
select top 1 @NodeToBeMovedTosLastImmediateChildMyKeyValue = _
[My Key] from TreeTable where
charindex(@DelimiterOrSeparatorValue, [My Key]) = 0 order by [My Key] desc;
set @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart =
unicode(substring(reverse
(@NodeToBeMovedTosLastImmediateChildMyKeyValue), 1, 1));
if @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart = _
@IntValueOfLastCharInSymbolRange
begin
update TreeTable set [Parent ID] = null, [My Key] =
@NodeToBeMovedTosLastImmediateChildMyKeyValue + _
@FirstCharInSymbolRange where
[My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] =
@NodeToBeMovedTosLastImmediateChildMyKeyValue + _
@FirstCharInSymbolRange + _
@DelimiterOrSeparatorValue + substring([My Key], _
len(@MyKeyValueOfNodeToBeMoved) + 2, len([My Key]) -
len(@MyKeyValueOfNodeToBeMoved) - 1) where [My Key] like
@MyKeyValueOfNodeToBeMoved + @DelimiterOrSeparatorValue + '%';
end
else
begin
set @NewMyKey = substring(@NodeToBeMovedTosLastImmediateChildMyKeyValue, 1, _
len(@NodeToBeMovedTosLastImmediateChildMyKeyValue) - 1) + _
nchar(@IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart + 1);
update TreeTable set [Parent ID] = null,
[My Key] = @NewMyKey where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @NewMyKey + _
@DelimiterOrSeparatorValue + substring([My Key],
len(@MyKeyValueOfNodeToBeMoved) + 2, len([My Key]) - _
len(@MyKeyValueOfNodeToBeMoved) - 1)
where [My Key] like @MyKeyValueOfNodeToBeMoved + _
@DelimiterOrSeparatorValue + '%';
end
end
else
begin
select top 1 @NodeToBeMovedTosLastImmediateChildMyKeyValue = _
[My Key] from TreeTable where _
[My Key] like @MyKeyValueOfNodeToMoveTo + _
@DelimiterOrSeparatorValue + '%' and _
(len(@MyKeyValueOfNodeToMoveTo) - len(replace(@MyKeyValueOfNodeToMoveTo, _
@DelimiterOrSeparatorValue, ''))) + 1 = _
(len([My Key]) - len(replace([My Key], @DelimiterOrSeparatorValue, '')))_
order by [My Key] desc;
if @NodeToBeMovedTosLastImmediateChildMyKeyValue is null or
len(@NodeToBeMovedTosLastImmediateChildMyKeyValue) = 0
begin
update TreeTable set [Parent ID] = @ParentIDOfNodeToMoveTo,
[My Key] = @MyKeyValueOfNodeToMoveTo + @DelimiterOrSeparatorValue +
@FirstCharInSymbolRange where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @MyKeyValueOfNodeToMoveTo + _
@DelimiterOrSeparatorValue
+ @FirstCharInSymbolRange + _
@DelimiterOrSeparatorValue + substring([My Key], _
len(@MyKeyValueOfNodeToBeMoved) + 2, len([My Key]) - _
len(@MyKeyValueOfNodeToBeMoved)
- 1) where [My Key] like @MyKeyValueOfNodeToBeMoved + _
@DelimiterOrSeparatorValue + '%';
end
else
begin
set @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart =
unicode(substring(reverse(@NodeToBeMovedTosLastImmediateChildMyKeyValue),_
1, 1));
if @IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart = _
@IntValueOfLastCharInSymbolRange
begin
set @NewMyKey = @NodeToBeMovedTosLastImmediateChildMyKeyValue + _
@FirstCharInSymbolRange;
update TreeTable set [Parent ID] = @ParentIDOfNodeToMoveTo, [My Key] =
@NewMyKey where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @NewMyKey + @DelimiterOrSeparatorValue +
substring([My Key], len(@MyKeyValueOfNodeToBeMoved) + 2, _
len([My Key]) -
len(@MyKeyValueOfNodeToBeMoved) - 1) where
[My Key] like @MyKeyValueOfNodeToBeMoved + _
@DelimiterOrSeparatorValue + '%';
end
else
begin
set @NewMyKey = _
substring(@NodeToBeMovedTosLastImmediateChildMyKeyValue, 1,_
len(@NodeToBeMovedTosLastImmediateChildMyKeyValue) - 1) + _
nchar(@IntValueOfNodeToBeMovedTosLastImmediateChildMyKeyValueLastPart_
+ 1);
update TreeTable set [Parent ID] = @ParentIDOfNodeToMoveTo,
[My Key] = @NewMyKey where [My Key] = @MyKeyValueOfNodeToBeMoved;
update TreeTable set [My Key] = @NewMyKey + @DelimiterOrSeparatorValue +
substring([My Key], _
len(@MyKeyValueOfNodeToBeMoved) + 2, len([My Key]) -
len(@MyKeyValueOfNodeToBeMoved) - 1) where [My Key] like
@MyKeyValueOfNodeToBeMoved + @DelimiterOrSeparatorValue + '%';
end
end
end
end
end
GO
insert into TreeTable ([Parent ID], [My Key], [Data]) values(NULL, 'A', 'Akshay Srinivasan');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(NULL, 'B', 'Douglas Mitchell');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(1, 'A.A', 'George Yates');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(2, 'B.A', 'Dan Brown');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(3, 'A.A.A', 'Chris Jones');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(4, 'B.A.A', 'Matt Daniels');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(1, 'A.B', 'Andrew Brown');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(3, 'A.A.B', 'Timothy Cook');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(3, 'A.A.C', 'Jane Franklin');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(1, 'A.C', 'Zachary Cage');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(3, 'A.A.D', 'Nancy Carter');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(1, 'A.D', 'Bill Smith');
insert into TreeTable ([Parent ID], [My Key], [Data]) values(3, 'A.A.E', 'Frank Richards');
History
- 23rd October, 2006: Initial version
- 16th May, 2020: Major updates
