Since you mention MySQL I assume that's what you're using to persist data. Storing a tree in a flat database is kind of a challenge. This page (http://www.sitepoint.com/article/hierarchical-data-database) suggests two ways: adjacency lists, and modified preorder tree traversal. MPOTT is a cute idea, but that's about it. It will make your database schema more complex, make your algorithms more complex, and require preexisting entries to be changed when new ones arrive. It's not faster than doing things in memory, and it's just asking for trouble.

Try using adjacency lists and reconstructing the tree in memory each time you serve it. This will let you get away with a single query for both reading and writing. The dev.mysql.com link you mention warns against using the adjacency list model, but that's because it's an area where MySQL itself is inadequate. It's fine when you fix things in another language.

Here's a minimal schema:

topic, id, parent, payload

ID is unique and non-zero. Parent is the ID of the parent node (0 if top-level). Topic is shared by all comments in a given topic. When you select, select by topic and then recreate your tree by going through and reestablishing "children" lists for each of your parents. You can then use traditional tree algorithms.

This method is easily modified to support caching.

id, date, topic_id, parent_id, score, payload

For example, say that your comments table stored the user id, the post id, the parent comment id (where the parent is the one the user clicked "reply" on), the vote count, and a timestamp. Then to render a page for all of the comments for a particular post, you could just pull all of the comments keyed by that post id and then order/arrange them however you want in your application code, such as by timestamp or number of votes. This doesn't require any tricky db writes and generally removes load from the db (which is desirable since its the hardest part of the app to scale).

The harder part is dealing with a case like the user comments page on neww.yc, where you show all of the user's comments along with of the descendants of those comments. Aside from the traditional approaches to storing hierarchies in relational dbs like the ones you linked to, I know of two other possibilities. One is to store the path of nodes to the root as lexicographically-comparable strings. The other is to create a separate table that stores ancestry relationships, in which for each node you have one row for each of its ancestors in the tree up to the root. Again, both of these approaches would allow you to pull out exactly the comments that you needed, but you would have to do the arranging in the application code.

7.401 7.40101 7.40102 7.4010201 7.40103 7.4010301

The downside was that it wasn't nearly this straightforward -- numbers seemed to be assigned haphazardly. And the scheme wasn't documented well, so it was nearly impossible for new programmers to understand.

I would not recommend this approach again. If you need high-performance searches for descendants, a separate table relating ancestors to descendants will be much more straightforward in the long-run.

2) If you do decide to use the database, you can increase the write speed of the nested sets model by leaving large gaps between the left and right values.

That is, if the single child of the root node has left and right values of 0 and 1000, and you insert another child, you give it left and right of 1000 and 2000, and update the parent.

Then you'll only have to renumber if you get a wicked long thread.

Anyway! The relational model uses tables to model all data. Though you can squeeze a comment tree into a relational data mode any number of ways, it is most clearly expressed by a hierarchical model as in XML, S-exprs or a tree data type in your favorite language.

So I'm not saying it can't be expressed as relational data, what I mean is that that representation is not its most natural or useful form.

At work I use a query like:

    select s1.id, s2.id, s3.id, s4.id ...
    FROM subject s1
    LEFT JOIN subject s2 WHERE s2.id=s1.parent
    LEFT JOIN subject s3 WHERE s3.id=s2.parent
    LEFT JOIN subject s4 WHERE s4.id=s3.parent
    ....
    WHERE s1.id=?

So, while you can model a tree as relational data, it's not a good match.

http://www.evolt.org/working_with_hierarchical_data_in_sql_u...

This allows all children (or parents) to be fetched in a single query. A suitable "order by" clause also groups them together for easier processing in one pass.

The cost is the same as any denormalisation - additional updates and integrity issues - so it isn't a no-brainer but it's probably a win in most such situations.

A classic read is jwz's article on threaded messages ~ http://www.jwz.org/doc/threading.html jwz was a key hacker on mozilla ~ http://en.wikipedia.org/wiki/Jamie_Zawinski

function article($link){

print_story($link->id);

print_comment(0,$link->id);

}

function print_comment($parent_id, $link_id){

$comments = $db->get_col("SELECT comment_id FROM table_comments WHERE comment_link_id=$link_id and comment_parent = $parent_id ORDER BY comment_votes DESC");

if ($comments) {

		$comment = new Comment;
		foreach($comments as $comment) {		
				$comment->print();
			}
				print_comment($comment_id,$link_id);
		}
								
	}

TABLE `table_comments` (

  `comment_id`, `comment_parent`, `comment_link_id`, `comment_votes`

If you store and manipulate all the data in memory, I don't see why this would be that bad?

Look at Slashcode (http://www.slashcode.com/), the code that powers Slashdot. They have quite a few threading features and they obviously figured out performance issues.

Is there any reason why that won't work?

When you store the tree on the DBMS, you have some algorithtms to do it well. For Example, the Nested Set (check the link up).

In that algorithm, the nodes are stored in a hierarchy that does not have any information about the votes.

So, you have a perfect tree, but with the first vote, you must update all the structure to reflect the new order of the child.

Nested set is great for speed reading, but not for writing often.

Sorry if I'm not very clear.

I was testing rails plugins : acts_as_nested_set and acts_as_better_nested and all have the same problem.

However, nested sets are more elegant. I believe the best approach would be to do the reordering in the application. Retrieve the comments in arbitrary order (probably chronological), and sort the siblings by votes just before you render.

When you need to view a page of comments that has not been loaded, load it into cache and then use your cache from there on out. When updates come in, write them directly to the cache, re-sort the cache as necessary, and then have the database updates run in the background.

For the cache tree model I use something like:

{'root_comment_id':123,'children_sorted_by_points':[]}

Cache expiration left as an exercise for you.

This can very easily handle something the size of hacker news.

edit: And this easily handles "many reads and many writes and an ever-changing order".

Would be a good idea to model the three on XML and store complete trees on the dbms? (thinking loud!) :)

Is here the solution? http://arclanguage.org/item?id=3426