mysql select - how to retrieve a result for threaded/nested messages?

Question

I'm creating a threaded message board and I'm trying to keep it simple. There's a message table, and then a replies table that has an 'reply_id' field that can be null to indicate a top level response, or a value that indicates a threaded response.

I'm a bit confused on how to do a SELECT call on this type of table though?

Reply
-id (every reply gets a unique id)
-message_id (the message it is replying to)
-reply_id (the id of the reply it may be replying to - for threading)
-reply

I know this can be a complex problem, especially for performance, but I'm really just looking for the most basic solution to this.

thanks...

Answer 1

You're using the naive "textbook" way of storing trees, i.e. store a reference to the immediate parent. This design is called Adjacency List. There are other solutions:

• Path Enumeration, where you store in each node of the tree a string encoding all its direct ancestors.
• Nested Sets, a clever approach by Joe Celko where you use two numeric values per node to bound all its descendants.
• Closure Table (or Adjacency Relation), where you use a separate table to list every ancestor-descendant pair.

See my response to "What is the most efficient/elegant way to parse a flat table into a tree?" for references and examples of the Closure Table design.