Normalized database structure for a forum

Question

The common normalized structure of database for a forum is to store all posts in a table where a column define the thread number. To display a thread, we need to perform SELECT with WHERE clause for the thread number (sorted by date). In this case, we deal with a very long table for every query.

Is it really the best way to store posts and threads for a forum?

It is more complicated for a Q&A like stockexchange projects, as in addition to answers (i.e. identical to posts in forum), each answer can have comments.

What is the most efficient database structure for a large website like stackoverflow?

Answer 1

It's far from being as large as SO, but in my application, the model I chos was to have each post have

• a FK to its parent post (root posts have null in this column)
• a FK to the root post (root posts have their own ID in this column, which is a bit awkward to insert new root posts, but helps for queries)
• a FK to their forum

This allows getting easily

• the root posts of a forum (searching for posts with a null parent)
• all the messages in a thread at once (searching all the posts having a given root)
• presenting the thread in flat mode (per date) or in tree mode (since each post knows its parent)
• the last posts in a given forum (searching the latest post grouped by forum)

Answer 2

A faster way to query is a mix between a trie and a nested set i.e. celko-tree. For example you can use the thread id to build a ternary trie with additional left and right id for the nested set query. The complicated thing is to insert or delete from this tree. Or you can take a kart-trie with a hash-key to search for left and right. But I think a nested set alone might already be sufficient because then the id is inorder.