Hierarchical Data using mysql

Storing hierarchical data in a relational database is a classic problem. Relational databases are not really designed for this purpose, because they store data in flat rows. Storage is actually the least of our problems. Imagine a commenting system with an unlimited level of nesting in replies. This is easy to store in a relational database:

comment_id	body	parent_id
1	JungleDragon rocks
2	No it doesn't!	1
3	Oh yes it does!	2
4	The economy sucks
5	True	4

For the sake of simplicity, I have omitted other comment fields such as author, date, etc. The table shows that we can easily store unlimited levels of nesting by simply linking to the parent of the current comment. Comments that have no parent are the root comments, the others are leafs. If we would apply a foreign key to the parent_id column and link it to the id column we even get full referential integrity. 
So far so good? Yes, but the real problems start when we want to query that table for useful stuff. Imagine the following tasks:

• Get the full comment tree sorted in the correct order. Hint: you cannot use date sorting, since replies can be made anywhere and must be positioned below their parent at all times.
• For each comment in the tree, we want to know how deep it is (how many levels deep), so we can use that for indenting the comment below its parent.
• For each comment we want to know how many replies there are, no matter how deep in the tree.

None of the above tasks can be queried efficiently using the table we started with. The problem is that since we do not know how many levels deep the hierarchy is, we need to make recursive calls, leading to many queries to the database, high memory usage in our scripts and generally a system that does not scale.
As said, this is a classic problem, and luckily there are existing solutions and patterns for this. This article explains four different approaches, I highly recommend it. In summary, these are the four methods:

• Recursive. The approach we already discussed. This approach is inefficient and does not scale.
• Stack. This one is not much different from the recursive approach. The idea is that you build a stack of hierarchical data by looping through the rows, typically inside a stored procedure. Once you have the stack built, it is very easy to use and query, however, it still requires a lot of database connections.
• Modified Preorder Tree Traversal. This surely is the most sophisticated, but also most complex, of the methods to work with hierarchical data. I encourage you to read the full description to really understand it. The principle of this method is that we assign smart numbers (left and right) to each leaf in the tree, these numbers indicate the relative position of the node towards other nodes. With a tree preordered like this, querying the hierarchical data becomes very fast and easy. There is a major downfall though: as soon as you insert or change something in the tree, it has to be rebuild. This will lead to many update queries, and these are expensive. The larger the tree, the larger the time of inserting a new node.
• Flat table model. Surely we know that if we could preprocess things like the level of the comment (how deep is it) and the rank (sort order), querying would become much easier. The author also admits that this does shift the performance problem to the writes: upon inserting a comment, all others ranks have to be recalculated. Anyways, the idea of this model is that you store essential attributes of the tree, instead of calculating them each time we retrieve the tree. Kind of like a tree cache.

Based on the options presented so far, it seems the flat table model looks promising, yet it does have a major limitation: a very expensive write operation. Luckily, one of the commenters of the article posted a way around this. I have taken his idea as a basis, and extended it somewhat.
The Flat Table Model done right
Let's just get to it right away. Here's my(heavily inspired) solution:

comment_id	body	parent_id	lineage	deep
1	JungleDragon rocks		1	0
2	No it doesn't!	1	1-2	1
3	Oh yes it does!	2	1-2-3	2
4	The economy sucks		4	0
5	True	4	4-5	1

Instead of using a rank, we are using a lineage. They have the same purpose (correctly ordering the comments), it's just that a lineage has one major advantage: it never needs to be updated! As you can see, the lineage column displays the hierarchy ids in a flat column (from highest parent to lowest child). This field is calculated upon insertion, no other inserts need to take place. The deep column simply sets the nesting level of the comment, which is handy when we need this value for indentation later on. By storing it, we require no recursive queries at all.
Let's go into a little bit more detail concerning the insertion of a new comment. Here's how it works:

• in our save routine of a new comment, we check whether it came from a parent (is parent_id set?)
• if so, we do a query to retrieve the parent row
• next, we calculate the lineage and deepness of the new comment. For lineage, we use the parent's lineage. For deepness, we use the parent's deepness + 1.
• we now insert our new comment. next, we use the returned comment id of the new comment, add it to the lineage of the newly created comment, and save it again (update).

All in all, we are retrieving a row, inserting one, and updating one. Considering the other highly inefficient methods and knowing that most people will read comments and not write them, this is pretty awesome. We have no recursion, not even a regular loop.
Querying this structure is even better. It is super easy to get all comments in the right order, get the indentation, and even the replies per comment, no matter how many levels of nesting we have. This query kind of combines these three tasks:
SELECT c.id, c.user_id, c.body, c.deep, c.lineage, c.parent_id, (SELECT COUNT(*) FROM comment where comment.lineage LIKE (CONCAT(c.lineage,'%')) AND comment.lineage!=c.lineage) as replies
FROM comment as c
order by c.lineage
Careful readers will see that we are using a subquery to count the replies for each comment. This part does have some performance overhead, but not much. If you do not need to show the number of replies to each comment, leave it our for even faster results. Or, you could take this even further by storing the number of replies in the database. The downfall of that approach is that you will need to recursively update all parents of the current comment row. That's not as bad as it sounds, it is not likely that you will have more than a handful of nesting levels for a single comment, in fact, most will have none, one or two.
Referential integrity
What about referential integrity? Since we have flattened the lineage and deep columns, we have lost some of that. No worries though, we are keeping our referential parent_id -> id foreign key. We do have referential integrity at the foundation. Should anything go wrong with the lineage or deep columns, then we can easily use the parent_id -> id relationship to "rebuild" those values.

Usage
The advanced flat model is optimized for a comment system, it should not be used everywhere. Particularly it is suitable for wide trees (little nesting), not deep trees. The reason for this limitation is the lineage column, which flattens the hierarchy in a single column. When there are too many levels of nesting (let's say over 20), a different model may be more suitable.
Yet another way
Throughout my online research, I found yet another way to work with hierarchical data. This approach is again a flat model approach, but this time the author reserves one column per nesting level in the table to store the deepness. The problem is that this results in a hardcoded nesting level limit. The other problem is that it is patented. Go figure. That's like patenting breathing.
Conclusion
There are multiple approaches towards storing and retrieving hierarchical data in (my)SQL, but for comment systems and other wide tree hierarchies, I hope you like my tweaked flat model approach. It has no recursion, not even loops, fast retrieves, the least writes, and a solid foundation of referential integrity. Credits go out to the author of the article and the commenter that suggested the lineage method. I only extended those ideas a little bit.
In closing, I like to end with a small tip. In many online examples, I see people looping through a depth counter to append things like spaces for indentation. This is not needed, almost every language has a function for this, here it is in PHP:
str_repeat("   ",$row['deep']);
...where the first param is the indentation string, and the second param is the number of indentations.
Enjoy!