I once heard of a system for representing threaded comments in a relational database, wherein the ID of each comment was a slash-separated list of its ancestors, e.g.:<p>1 Initial comment<p>1/1 Re: Initial comment<p>1/2 Re: Initial comment<p>1/2/1 Re: Re: Initial comment<p>1/2/2 ...<p>These sorts of IDs have the wonderful property that you can efficiently select any subtree using a LIKE query, e.g. "SELECT * FROM comments WHERE path LIKE '1/%'". These queries are efficient because they use string btree indexes. And the results may even be sorted the right way, provided you have monotonically increasing IDs within each level.<p>I think I read about this technique being used on Slashdot a few years ago, but I can't remember the name or find any reference. Still, it seems like a way to achieve the same benefits that the OP cites for comments with PostgreSQL's ltree support on any database with reasonable string indexing.<p>Anyone know the name of that technique?
If you are using Django, <a href="http://bitbucket.org/tabo/django-treebeard/overview" rel="nofollow">http://bitbucket.org/tabo/django-treebeard/overview</a>, is a great app to use. It implements several different tree storage methods.
I used these for a commenting system as well, they're really quite amazing. There's basically three options when storing a tree in a relational database - adjacency lists which are slow to read, nested sets which are slow for writes, and materialized path, which is slow for moving around nodes.
It's good to have a fourth option which is straightforward to implement and has excellent performance.
Just wanted to throw an update over here. The examples in my post are specifically geared towards a basic threaded comment structure, which Disqus is not. Our usage is much more complex than this example, but we are able to handle sorting by dynamic data (which we use in our "Most Popular" sort algorithm).<p>In other words, recursion still works, and in our tests has proven faster than doing it at the application layer (no matter how you sugar coat it).
I tackled this problem on appengine a while ago.<p>Turns out that the average discussion thread has few enough comments that they can be fetched from the db in one call (e.g. by the thread_id). This makes even deeply nested comments fairly simple to query for, and then it is quite easy to rebuild the tree in memory.<p>I think reddit uses this method too.
The Oracle equivalent of this functionality if called CONNECT BY PRIOR:<p><a href="http://ss64.com/ora/connectby.html" rel="nofollow">http://ss64.com/ora/connectby.html</a><p>I used it back in 2002 to build some messageboards and it was pretty effing magical. Glad to see equivalent functionality finally make it to OSS.
Personally I just sort everything in memory like reddit, since I need to traverse all branches to calculate weighed scores, which is a balance of vote counts and age. I think reddit/HN do something similar? I wonder how Disqus handles this.<p>I'm not really sure how to do that in SQL.