If you're trying to mimic this forum with a database solution, it's going to be a pain. PG's keeping this stuff in memory, almost certainly as the tree that it is.

edit on the edit: scratch that.

I mentioned a possible solution here: http://news.ycombinator.com/item?id=33902, but I'm really commenting because there's a really cool connection between PG's approach of storing it as an in-memory tree and my approach of a 2048-bit index:

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.

You probably don't even need to be using the word "bit" unless you're writing something a lot more performance intensive than a forum.

Optimized ob. quote:

"Premature → evil."

Just thinking off the cuff here, but couldn't one store a lisp-style list as a string in a relational database. If I was using Ruby on Rails, I could simply build a simple lisp interpreter in Ruby to parse the string, then capture it as an in-memory tree. This way I would only have active items in memory and could use some of the advantages of the standard web development platforms for whatever else I was doing.

Edit: See Ruby/Lisp for one such already built interpreter.

Sure you could. You could also select all comments on the item and rebuild the tree in-memory, as Vlad suggests elsewhere on this thread. The code isn't even as hard as I'd thought it'd be:

  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)

The nifty thing about storing it in the database is that you need no application-level post-processing, you can take advantage of the DB for ad-hoc queries (what if you want to show subtrees of all posts by a certain user, like the "threads" page here?), and it happens to map to a set of simple and fast operations provided by most databases.

After some reflection, I suppose my only hesitation with this method is that it locks one into dealing with the comments in a particular way, whereas the lisp model I outlined is easily adaptable to a variety of schemas.

However, I'm not sure how else one would want to model things. Must think more...

This is closely resembles the way i did it... With recurrsive includes (views). Performs flawlessly.

Why are you using a database, in this case? Aren't you better off serializing your tree using the native methods of your language? (e.g., with pickle.dump() in Python.)

Database for searching for by the item (news story, game, journal entry), pickle or sexprs for the individual comment threads. The database helps you manage the hopefully large number of news stories you'll get. The tree takes care of individual comments for a single news story.

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.

Is this what you are actually doing? How do you store the pickle output?

I'm not - I'm using the approach here: http://news.ycombinator.com/item?id=33888 . That gives me much more flexibility in picking out individual comments from a thread, returning all comments by a specific user, getting all comments posted today, etc. I'm just recognizing this as another possible way to solve the problem, if you don't care about the extra functionality..

As for storing the pickled output:

  dbh.execute('UPDATE articles SET comments = $comments WHERE news_id = $id', 
              comments=pickle.dumps(article.comments))

The comments field can be a normal TEXT field, since the default format for pickle is ASCII-based.

Okay, makes sense. I hadn't read your earlier posting that carefully before, but it sounds better than what I had in mind.

The question has to do with storage. I suppose you could serialize it and store in a flat file, but will this beat the DB access time, even if there is extra time needed for interpretation?

What's hard about threaded comments, exactly?

how you store them, to how they are fetched, to how they are displayed and arranged according to popularity (i think thats how news.yc works) on every vote.