Hierarchies and trees are a challenge in SQL.
This is an example of a very simple tree
With our application the Parent ID and ID columns are both GUIDs. To help with readability I have used numbers in the examples.
This looks like
The table structure above will work very well in most cases. It's very easy to select the parent of an item and select the children of an item. You can easily add new items or delete items. You get problems when you need to find things like all the decedents of an item.
You can use CTE (common table expressions) but under heavy load and with lots of data it just does not work.
We looked at the nested model. This does not work with simple deletes and inserts. (http://www.developersdex.com/gurus/articles/112.asp )
The final approach we took was to add an incremental number to our table and a row path column. As follows :
When we generate the rowpath we pad it with zeros so each row number starts at the same place. We do not use delimiters we used fixed spaces.
This is a simple representation of how the table will look. This is simple as I am just padding the rowpath with 2 zeros (not 16).
This is an example of how the data looks in SQL with it padded with 16 zeros.
To get the child items, then we need to run the following SQL :
@path is the path that we need to find the child items from
@pathplusone is our path plus one, see the function below for how to increment this.
Select Name from Table where RowPath > @path and RowPath < @pathplusone
We increment the path with the following SQL
CREATE FUNCTION [dbo].[IncrementRowPath]
@VarBinary VARBINARY(160) = 0x0000000000000000
DECLARE @Result VARBINARY(160)
-- If the data is the wrong size.
IF(@VarBinary IS NULL OR DATALENGTH(@VarBinary) % 8 != 0)
SET @Result = 0x0000000000000000
-- Increment the last 8 byte segment.
DECLARE @LastSegment BIGINT
SET @LastSegment = CAST(SUBSTRING(@VarBinary, DATALENGTH(@VarBinary) - 7, 8) AS BIGINT)
SET @Result = SUBSTRING(@VarBinary, 1, DATALENGTH(@VarBinary) - 8) + CONVERT(VARBINARY(8), @LastSegment + 1)
I hope this helps you out with trees.
The only issue is that you need and index on rowpath, this index is going to be large, but in our testing and our live implementations it's not caused an issue.