Hierarchies (trees) in SQL Server 2005

re: Hierarchies (trees) in SQL Server 2005

Jeff Moden — Thu, 26 Jul 2012 00:58:37 GMT

I know this is an old thread but ran across it while doing a bit of research. I've got to ask, where is the code that built the 20,000 row sample and where is the code that you actually tested?

re: Hierarchies (trees) in SQL Server 2005

Kenorasis — Sat, 22 Oct 2011 15:11:03 GMT

It seems to me that the Nested Sets approach is storing more information than the others, namely, the ORDER in which sibling nodes appear. In the example above, if we wanted Denise to appear to the left of Charles, we would need another field (and a mechanism to manage the value of that field) to store the order in both the Adjacency and the Path techniques.

I know the original post is a bit old at this point, but it would be interesting to see how one could build a mechanism to store the order of sibling nodes into the Adjacency and Path technique and then compare all three for speed.

re: Hierarchies (trees) in SQL Server 2005

Kalin — Fri, 10 Jun 2011 16:12:34 GMT

In support of Marc Buzina's approach, here is my experience with a project that currently holds around 37,000 tree nodes and is always expected to grow, although not very fast.

We started as usual with the adjacency list model. As the tree kept growing we moved to nested sets trying to improve response time. The tree kept growing and timeouts and concurrency problems made it clear that we needed another aproach. (Our nested sets implementation did not use gaps and inserts/updates/deletes involved a lot of recalculations of intervals. Also most probably it was not the most optimized implementation.) We came across something called "Transitive closure" which maps to the structure proposed by mbuzina.

Now our Tree table has three columns: NodeId, ParentId, SiblingNumber. The TreeHierarchy table has AncestorId, DescendantId, Distance and holds about 240,000 records. It is maintained through triggers on the Tree table. Insert/update/delete of a node now affect only a small number of records in TreeHierarchy, so deadlocks and timeouts do not worry us any more. Retrieving the whole tree takes less than 0.6 sec. We never need to do this anyway, because the end user would have to wait a long long time for the browser to show all 37,000 nodes, so we load on demand only branches that the user decides to delve deeper into. The maximum depth currently is 11, and the most "fertile" parents have between 300 and 680 children.

re: Hierarchies (trees) in SQL Server 2005

Jon — Mon, 16 Nov 2009 11:28:06 GMT

I don't know this Celko. Wikipedia says:

He is often corrected by product experts including a number of the SQL Server MVP's which lead to protracted discussions which more often than not he comes out losing.

All I know is he is a brag who's not helping average programmers... I have 20+ experience and paid $1000s of a day. Ashol. Same with you Chandrashekar. I bet you dont even know what you are saying.

re: Hierarchies (trees) in SQL Server 2005

OrbMan — Thu, 10 Sep 2009 15:23:48 GMT

The high value for all descendents of the path model makes me think the path column was not indexed - can you confirm whether it was or not?

re: Hierarchies (trees) in SQL Server 2005

Niclas — Fri, 08 May 2009 01:31:43 GMT

Hi there,

I have a problem which i wonder if you could point me in direction how to solve.

I have a tree structure where each node have a "rating" column (int). For "composite" nodes, nodes with children the rating column should take the value of the max value of all its children. What kind of structure do i represent such a tree best in?

re: Hierarchies (trees) in SQL Server 2005

Yoseph — Fri, 03 Apr 2009 12:37:27 GMT

When using Nested set, if you want to retrieve all the tree (root node and all of its descendants), all you need to do is: SELECT * FROM tree ORDER BY left ASC. The process of generating the tree is supposed to be handled by your application. So the query needed is only 1, not 6072.

You can see the implementation of this tree in PHP ORM framework (Propel) ->

http://propel.phpdb.org/trac/wiki/Users/Documentation/1.3/Tree/NestedSet

Here is some code of the implementation of retrieving tree:

public static function retrieveTree(PropelPDO $con = null)

{

$c = new Criteria(TreePeer::DATABASE_NAME);

$c->addAscendingOrderByColumn(self::LEFT_COL);

EXECUTE QUERY:

SELECT * FROM tree ORDER BY lft ASC

$stmt = TreePeer::doSelectStmt($c, $con);

if (false !== ($row = $stmt->fetch(PDO::FETCH_NUM))) {

$root = new Tree();

$root->hydrate($row);

$root->setLevel(0);

$tree = self::hydrateDescendants($root, $stmt);

$stmt->closeCursor();

return $tree;

}

return false;

}

Note: only 1 query is executed.

re: Hierarchies (trees) in SQL Server 2005

mbuzina — Thu, 05 Feb 2009 11:41:18 GMT

I am missing the classical datawarehouse approach. I know it is mostly focused on querying, but in my personal experiance, the insert performance is not too bad, depending on the model of inserts.

I have successfully used a combination of adjencency with a cache table for holding all relationships. I would have the following cache table

emp_cache

descendant,ancestor,distance

2,2,0

1,1,0

1,2,1

3,3,0

3,2,1

4,4,0

4,3,1

4,2,2

5,5,0

5,3,1

5,2,1

Additionally I would add a depth column to the base table, which allows a quicker computation of the distance value inside the trigger maintaining the cache and have the cache table indexed (depending on your query patterns). Inserting, updateing & deleting is done exactly as with adjacency, which makes sure there are no loops at all. Querying will use the cache table (& depth column). Querying the cache is quite natural to sql.

I used this to handle a cost center structure which was 17 levels deep and handled approx. 15.000 nodes.

re: Hierarchies (trees) in SQL Server 2005

dan — Wed, 26 Nov 2008 05:06:28 GMT

To the person making comments that sound a bit nasty, and mentioning NP-Complete. it may come as a surprise to you, but not everyone releases everything they have, and there are indeed some solutions out there you have not heard of.

re: Hierarchies (trees) in SQL Server 2005

Cesar — Sat, 31 Mar 2007 08:35:21 GMT

I know it is too late to ask, but where is the data to test your experiment?