Reordering can be done just by looking at all records whose IDs contain the parent as a prefix and have a length 2 greater than the parent, and then renumbering them. This should be computationally feasible in most cases.
This does limit users to 65,536 replies to a single comment, and a maximum comment nesting depth of 127. Based on my experience with some very active LiveJournal threads, I considered these to be acceptable limitations (LJ limits comments to 5000/post anyway). A nesting depth of 127 would be nearly 2400 pixels over, so it's not like it'd all fit on one screen anyway.
Also, each comment should have a newsid field that points to the original newstopic. The left-most posts would have the parentid and newsid that were the same (or parentid can be zero, depending on how you do it). But any replies would have the parentid to the parent comment, but the newsid would still point to the newstopic. Then you just run an SQL query to find all comments with the newsid for that newstopic. You won't have to join any tables. After that, with everything in memory, you can just sort the way it has to be. Finally, you can cache the page in memory or a file in case the page doesn't change for the next set of visitors.
To simplify the recursive function (using data in memory, not in the database), you could also have another field, called indent, that stores the level in the comments.
You could find all the comments with one SQL statement (where newsid = news.id), then go through each level of each comment, and sort it that way.
You could even make the parentid field a double, so you would store 123.4 where 123 would be the parent and 4 would be the indentation level.
I guess the difference is, do you want to store everything in one field or have different fields for everything?
I think this gives the original poster many options to think about. To me, a recursive function would be easier to write than coming up with ways to combine multiple fields into one using MySQL.
I think the order of optimization is: 1) Optimize so you can use a cached result if it exists 2) If the cache is out of the date, try to make just one SQL call 3) don't use table joins 4) reorder the data as needed in memory, then save it to a cache
As far as the single SQL call goes, I don't think it matters whether you have 5 fields or 30 in the actual table as long as you only request the fields you need, but I could be wrong.
By the way, do you have any other interesting examples?
My solution was to store a comment thread in display order in the database with hinting as to how deep in the heirarchy the comment is. Optimizes for output, although with some cost every time something gets posted. Luckily, for most forums, views outnumber posts by hundreds of times.
The one issue that system has is that if you're doing a lot of reordering, let's say from quality scores. In that case you'll basically have to remake the thread after every post and after vote that makes a difference. Not recommended...
[edit] especially when the comments get reordered on votes.
edit on the edit: scratch that.
Y'know how in a typical CS datastructures course you'll have to build a heap, and then reimplement with an array? A heap is conceptually a balanced binary tree where every leaf is filled, while there's nothing tree-like about an array. However, your CS profs were trying to get across that any binary tree can be stored as an array, with the root in position 0, its leaves in positions 1 and 2, their leaves in positions 3, 4, 5, 6, etc. If a node doesn't have a leaf, that position in the array is empty.
Normally this is very inefficient - a totally-unbalanced (linked list) binary tree of length 20 would require a 1MB array to hold it. However, heaps are always perfectly balanced, so an array really is the most efficient implementation for them.
By restricting users to a certain number of replies to each comment (65,536), I'm effectively constraining an arbitrary tree structure to a 65,536-ary tree. Which can then be represented by an array. If held in memory, it'd be a very sparse and inefficient array.
But databases are excellent at storing sparse arrays. If I don't store a potential key, it doesn't take up any space in the DB. And with a good indexing system, I can reference any element in constant time (well, O(logN), but the log base for B-trees is so huge that it might as well be constants).
So, I'm really just applying some of the meta-principles of CS coursework to basic data structures. (Actually, I got the idea off a Slashdot posting and had to figure very little of this out on my own, but it's still really cool.)
Incidentally, there's apparently a deep connection between number systems and tree structures. You can read more about it in Chris Okasaki's Purely Functional Data Structures. Apparently, every number system corresponds to a data structure. For example, Peano arithmetic = linked lists, binary numbers = binary trees, fibonacci numbers = binomial heaps, etc. There's a short presentation on it here: http://www.informatik.uni-bonn.de/~ralf/talks/BCTCS.pdf, and I'd strongly recommend the book.
"Premature → evil."
Edit: See Ruby/Lisp for one such already built interpreter.
comments = dbh.query('SELECT * FROM comments WHERE news_id = $newsid')
response_tree = {}
for comment in comments:
comment.children = []
response_tree[comment.id] = comment
for comment in comments:
response_tree[comment.parent_id].children.append(comment)
However, I'm not sure how else one would want to model things. Must think more...
Many filesystems have trouble with large numbers of files in a single directory, as you'd get with eg. pickle tree to a file per item.
As for storing the pickled output:
dbh.execute('UPDATE articles SET comments = $comments WHERE news_id = $id',
comments=pickle.dumps(article.comments))