Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Handling Hierarchy Data in Database

I'm curious to know what the best way (best practice) to handle hierarchies are in regards to database design. Here is a small example of how I usually handle them.

Node Table

NodeId int PRIMARY KEY
NodeParentId int NULL
DisplaySeq int NOT NULL
Title nvarchar(255)

Ancestor Table

NodeId int
AncestorId int
Hops int

with Indexes on NodeId, AncestorId, Hops

Tables look like this:

Node Table

NodeId    NodeParentId    DisplaySeq    Title
1         NULL            1             'Root'
2         1               1             'Child 1'
3         1               2             'Child 2'
4         2               1             'Grandchild 1'
5         2               2             'Grandchild 2'

Ancestor Table

NodeId    AncestorId    Hops
1         NULL          0
1         1             0
2         1             1
2         2             0
3         1             1
3         3             0
4         1             2
4         2             1
4         4             0
5         1             2
5         2             1
5         5             0

With this design, I've found that with large hierarchies I can get an entire section of the hierarchy very quickly by joining on the Ancestor table for AncestorId = target NodeId, like:

SELECT *
FROM Node n
INNER JOIN Ancestor a on a.NodeId=n.NodeId
WHERE a.AncestorId = @TargetNodeId

It's also easy to get direct children as well

SELECT *
FROM Node n
INNER JOIN Ancestor a on a.NodeId=n.NodeId
WHERE a.AncestorId = @TargetNodeId
AND Hops = 1

I'm interested in knowing what other solutions you may have used for this type of thing. In my experience, hierarchies can get pretty hairy, and any way to optimize their retrieval is very important.

like image 695
Ryan Abbott Avatar asked Feb 25 '09 19:02

Ryan Abbott


People also ask

What is the hierarchy of data in database?

Hierarchical data is a data structure when items are linked to each other in parent-child relationships in an overall tree structure. Think of data like a family tree, with grandparents, parents, children, and grandchildren forming a hierarchy of connected data.

What is hierarchical data model in DBMS?

What is the Hierarchical Model in DBMS? The Hierarchical Model was the first database management system model. This concept uses a hierarchical tree structure to organise the data. The hierarchy begins at the root, which contains root data, and then grows into a tree as child nodes are added to the parent node.

What is example of hierarchical data structure?

Tree is an example of hierarchical data structure.


1 Answers

There are some vendor-specific extensions to do this, but my favorite db-neutral way comes from Joe Celko - google 'Joe Celko Trees and Hierarchies' or buy this book: link text

This is a very clever set-based way to go. Easy to query hierarchy. I added the 'parentID' field you have just because I ask the 'direct children' and 'parent' questions a lot and that speeds those up. But this is a wonderful way to get a 'ancestry' or 'descdent' query.

like image 155
n8wrl Avatar answered Oct 22 '22 13:10

n8wrl