How to store directory / hierarchy / tree structure in the database?

Question

How do i store a directory / hierarchy / tree structure in the database? Namely MSSQL Server.

@olavk: Doesn't look like you've seen my own answer. The way i use is way better than recursive queries :)

p.p.s. This is the way to go!

Solution 1

There are many ways to store hierarchies in SQL databases. Which one to choose depends on which DBMS product you use, and how the data will be used. As you have used the MSSQL2005 tag, I think you should start considering the "Adjacency List" model; if you find that it doesn't perform well for your application, then have a look at Vadim Tropashko's comparison which highlights differences between models with a focus on multiple performance characteristics.

Solution 2

If using Sql Server 2008 is an option: maybe you should check out new hierarchyid data type.

Solution 3

There also is the Nested-Set Model of Trees which has some advantages over the ParentID model. See http://www.evanpetersen.com/item/nested-sets.html and http://falsinsoft.blogspot.nl/2013/01/tree-in-sql-database-nested-set-model.html

Solution 4

Are you using SQL Server 2005? Recursive queries make querying hierarchical data much more elegant.

Edit: I do think materialized paths are a bit of a hack. The path contain non-normalized redundant data, and you have to use triggers or something to keep them updated. Eg. if a node changes parent, the whole subtree have to have their paths updated. And subtree queries have to use some ugly substring matching rather than an elegant and fast join.

Solution 5

I faced the similar problem with one of my projects. We had a huge hierarchy which will keep increasing forever. I needed to traverse it fast and then finding the right group after some complex validations. Rather than going to SQL Server and scratching my head how can I do it efficiently there when I knew that Recursive queries are the only viable solution. But do you really know if there is any optimization at all possible in Recursive Queries. Is there any guarantee that your hierarchy will not increase in future and one fine day you find out that your recursive queries are too slow to be used in production?

So, I decided to give a shot to Neo4J. It's a graph database with many useful algorithms in-built, amazingly fast traversal with decent documentation and examples. Store the hierarchy in Neo4J and access hierarchy using a Thrift Service (or something else). Yes you will have to write code which will integrate your SQL queries with Neo4J but you will have a scalable and more future-proof solution.

Hope you find this useful.

View more solutions

Comments

[NightOwl888]

@Ali - Your link is broken too!

[Ali]

@NightOwl888 Yes, it has become broken. I just spent 20 minutes googling and failed to find it... So I deleted the comment with the broken link.

[izilotti]

There are big tradeoffs when it comes to implementing this kind of solution. The recursive approach, which used to be my favorite, is elegant, but less efficient, since paths must be computed more frequently.