How to store a tree in SQL database

Question

I have to store a tree in a database, so what is the best way to do this? Show the method you use and name its pros and cons. (I am using SQL Server 2005)

Solution 1

I found the discussion in the SQL Anti-patterns very helpfull, as it also focuses on the drawbacks of every implementation.

Also, The slides 48-77 in this presentation reiterate that analisys.

Bottom line, there is no such thing as a generic tree, and no silver bullet for SQL trees. You'll have to ask yourself about the data, how and how much will they be selected, modified, will branches be moved around, etc, and based on those answers implement a suitable solution.

Solution 2

Well, the easiest way would be for a record to have a ParentID column so that it knows which record is its parent. This is a pretty standard practice. For example, an online store might have a hierarchy of product categories. Each category will have a ParentID. Example: The "Jeans" category in an clothing database might have "Pants" as the parent category. It's a bit harder if you want a record to indicate which are its children, unless you restrict the number of children. If you want a binary tree, you could have LeftChildID and RightChildID columns. If you allow any number of children, you could have a Children column with IDs delimited by commas (such as 1,4,72,19) but that will make querying rather hard. If your database allows for array types in columns, you can probably use an array instead of a delimited string, which would be easy to query - but I'm not sure if MS SQL Server supports that or not.

Other than that, it depends on what kind of data you are modelling, and also what sort of operations you plan to do with this tree.