How to store a tree in SQL database

Question

Hi,

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)

Answer 1

did you bother to search before you posted?

Answer 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.

Answer 3

try this: Hierarchies (trees) in SQL Server 2005

Answer 4

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

I found that a very helpful guide.

Answer 5

There are two general approaches

1. In each record, Store the Id of the parent in a nullable column (the root of the tree has no parent)

2. Use Joe Celko's nested set model technique explained here and (thanks to comment from @onedaywhen), also in what is the original source here

   Pros and Cons ?? !! you're kidding, right ?!

Answer 6

I have done this in the past by storing data as xml in SQL.

Answer 7

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.