I am building a blog - just to shapen my skills. Since leaving college I feel like I have been loosing my programming edge. I work in IT and I primarily work on Oracle databases as a developer.

Here is what I am building - a blog. I have already built a simple blog with post and comments. Now I want to extend it to so that comments can have comments as well. I can do it using mysql by adding parent-id, so every post has a parent-id and the root post or main post with parent-id null or 0. I could also do it using some kind of a data structure. Now that is what I actually want to do since I'll learn more that way.

So my question is: what is the best data structure to implement the requirement mentioned above. I am leaning toward a trie data structure. Any thought?

Recommended Answers

All 4 Replies

I think the Parent Structure would be the most optimal way of doing this IMO

Member Avatar for diafol

It can be done like this. Or a perhaps simpler method of the underscore method:

Have an underscore at the end for every hierarchical level except for top level comments (equivalent to parent_id = 0), e.g. where structure_prefix is varchar (?), depending on the number of allowed comments per branch and depth of comment tree.

comment_id  |  structure_prefix  | other fields ..
            1  |   NULL       (this is top level)
            2  |   NULL       (also top level)
            3  |   1_         (belongs to comment #1)
            4  |   1_         (also belongs to comment #1, but comes after comment #3)
            5  |   1_4_       (branch off comment #4)
            6  |   2_         (first reply to comment #2)
            7  |   1_         (third reply to comment #1 at this level)

You can retrieve all these in one go with the following SQL:

SELECT *, CONCAT(COALESCE(structure_prefix,''), comment_id) AS comment_order FROM comments ORDER BY comment_order

This will give the result:

Comment_id |  structure_prefix | ... | comment_order
                   1 |   NULL   | 1
                   3 |   1_     | 1_3
                   4 |   1_     | 1_4
                   5 |   1_4_   | 1_4_5
                   7 |   1_     | 1_7
                   2 |   NULL   | 2
                   6 |   2_     | 2_6

You can then use the structure prefix to note any changes to the levels and apply your indented divs / class hooks for css as appropriate.
The structure prefix for a new comment is set in the comment form as a hidden field.

This may provide a simpler route than recursion or complicated php array methods. The one-stop SQL for traditional parent_id fields I've seen require you to decide upon the maximum level depth, for example:

Select T1.Id, T1.Type
    , Concat( Coalesce( Concat(Cast(T4.Id As char(10)),','),'')
        , Coalesce( Concat(Cast(T3.Id As char(10)),','),'')
        , Coalesce( Concat(Cast(T2.Id As char(10)),','),''))
        As Hierarchy
From ExampleTable As T1
    Left Join ExampleTable As T2
        On T2.Id = T1.ParentId
    Left Join ExampleTable As T3
        On T3.Id = T2.ParentId
    Left Join ExampleTable As T4
        On T4.Id = T3.ParentId

from: http://stackoverflow.com/questions/10367229/sql-query-for-nested-records

well, if you look at it closelly it's :

Table : comment

reply_to         -> comment.id of the one it replies to
creation_date -> CURRENT_TIMESTAMP

Make sure that, you don't get this on X levels when saving, keep it maximum on two levels, parent and child. no "grand-parent" stuff because it will get complicated when rendering for the user, well you can eventually render it but it will probably look horrible.

While a threaded set of comments like this is probably best handled by a NoSQL database the necessity to deal with them in a relational database has exsisted for some time.

I would suggest looking at either Path Enumeration or a Closure Table to properly model a threaded conversation to n depth and still be able to CRUD the data with ease. Check out the following presentation as it provides some good illustrations and examples of four ways to solve this, including the two I have mentioned. http://www.slideshare.net/billkarwin/models-for-hierarchical-data

The presentation author has also written a detailed example on his blog of rendering a Closure Table. http://karwin.blogspot.com/2010/03/rendering-trees-with-closure-tables.html

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.