Adjecency List Model OR Nested Set Model, which data model should I use to store my hierarchiecal data?

Question

I have to store messages that my web app fetch from Twitter into a local database. The purpose of storing messages is that I need to display these messages in a hierarchical order i.e. certain messages(i.e. status updates) that user input through my application are child nodes of others (I have to show them as sub-list item of parent message). Which data model should I use Adjacency List Model OR Nested Set Model? I have to manage four types of messages & messages in each category could have two child node. One more question here is that what I see(realize) in both cases that input is controlled manually that is how reference to parent node in adjacency model or right, left are given in Nested List. My app fetch messages data from twitter like:

foreach ($xml4->entry as $status4) {
       echo'<li>'.$status4->content.'</li>';
       } 

So its no manual, any number of messages can be available anytime. How could I make a parent child relation among messages from it. At the moment, users enter messages in different windows that correspond to four types of messages, my app adds keywords & fetches those back to display in diff windows. All those messages are at the moment parent messages. Now how I make user enter a messages that could be saved into database as child of another.

Answer 1

When you say

depth of tree is 2 nodes. i.e. each parent msg could have two child nodes.

i get confused.

If each of the two child nodes can have more children then you are not taking about depth, but width of a branch of a node.

1) depth really = 2

If your max depth is really 2 (in another words, all nodes connect to root, or zero level nodes in 2 steps; yet in another words, for each node there is no other ancestor then parent and grandparent) then you could even use relational model directly to store hierarchical data (either through self join, which is not so bad with such low maximum depth or by splitting the data into 3 entities - grandparents, parents and children)

2) depth >> 2

If number 2 was the width and the depth is variable and potentially quite deep then look at nested sets, with two additional possibilities to explore

• using the nested set idea you could explore geom type to store hierarchical data, (the benefits might not be so interesting - few useful operators, single field, possibly better indexing strategy)
• continued fractions (based on nested set, tropashko offered generalization which seemed interesting as they promised to improve on some of the problems with nested sets; didn't implement it though so... do your own tests).

Answer 2

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

If you are going to have more or less deep trees of data (starting from each root node) consider using nested set, because AL will be slow.