How to order/sort a list where multiple users insert into different positions?

Question

Im making an app where multiple users can post comments above or below other comments. This is not a thread-type structure. It's more like collaborating on a Word document. Im having trouble designing the method these entries are sorted.

Using mySQL and PHP, sorting by time of entry doesnt work, and neither does sorting by comment position because the position changes if user posts inbetween other comments. I dont want to have to re-serialize comment positions for every new entry (what if there are thousands of entries and dozens of users doing the same thing).

What is the best way to design this?

Answer 1

What you are describing is a linked list. The problem is that they are usually hard to retrieve using just SQL. My solution is to use PHP to do the sorting upon retrieval.

Your table would look something like this:

CREATE TABLE page {
   page_id INT,
   first_comment_id INT
}

CREATE TABLE comment {
   comment_id INT PRIMARY KEY AUTOINCREMENT,
   page_id INT,
   next_comment_id INT
}

Your query is simple:

SELECT comment_id, next_comment_id 
FROM comment 
WHERE page_id = $page_id 
ORDER BY comment_id DESC

The important step is to massage the results from mysql_fetch_assoc() into an array that is indexed according to comment_id:

$result = mysql_query($sql);
$indexed_list = array();
while ($row = mysql_fetch_assoc($result)) 
{
    $indexed_list[$row['comment_id']] = $row;
}

Resulting in an array similar to this one:

$indexed_list = array(
    1 => array("comment_id"=>1, "next_comment_id"=>2),
    2 => array("comment_id"=>2, "next_comment_id"=>5),
    3 => array("comment_id"=>3, "next_comment_id"=>4),
    4 => array("comment_id"=>4, "next_comment_id"=>0),
    5 => array("comment_id"=>5, "next_comment_id"=>3));

The PHP function to sort them into displayable order is simple:

function llsort($indexed_list, $first_comment_id) 
{
    $sorted_list = array();

    $node = $indexed_list[$first_comment_id];
    array_push($sorted_list, $node);

    do
    {
        $node = $indexed_list[$node['next_comment_id']];
        array_push($sorted_list, $node);
    } while ($node['next_comment_id'] != 0 
        AND isset($indexed_list[$node['next_comment_id']]) );

    return $sorted_list;
}

You get first_comment_id from the page table. Of course, you still have to implement functions to insert a node and delete a node, but those are left as exercises for the reader. Don't forget to use transactions for inserting and deleting nodes.

More information on linked lists in MySQL:

• Fetching linked list in MySQL database
• Creating a linked list or similar queue in MySQL?
• Managing Hierarchical Data in MySQL
• Trees and Other Hierarchies in MySQL