How do I store a directory / hierarchy / tree structure in a database?

How do I store a directory / hierarchy / tree structure in a database? Namely Microsoft SQL Server.

Upvotes: 69

Answers (7)

JacquesB

Reputation: 42689

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.

Upvotes: 3

Andrew

Reputation: 2646

The question is similar to this question that was closed. I found answers to both questions very helpful in my pursuits, and they eventually led me to the MongoDB manual that presents 5 different ways to model tree structures: https://docs.mongodb.com/manual/applications/data-models-tree-structures/

While MongoDB is not a relational database, the models presented are applicable to relational databases, as well as other formats such as JSON. You clearly need to figure out which model is right based on the pros/cons presented.

The author of this question found a solution that combined both the Parent and Materialized Paths models. Maintaining the depth and parent could present some problems (extra logic, performance), but there are clearly upsides for certain needs. For my project, Materialized Paths will work best and I overcame some issues (sorting and path length) through techniques from this article.

Upvotes: 2

Rockcoder

Reputation: 8479

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

Upvotes: 9

Lars Truijens

Reputation: 43635

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

Upvotes: 6

Marut Singh

Reputation: 355

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.

Upvotes: 3

Troels Arvin

Reputation: 6411

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.

Upvotes: 26

Sklivvz

Reputation: 31163

The typical way is a table with a foreign key (e.g. "ParentId") onto itself.

Upvotes: 1

How do I store a directory / hierarchy / tree structure in a database?

Answers (7)

Related Questions