Cách sắp xếp/sắp xếp danh sách nơi nhiều người dùng chèn vào các vị trí khác nhau?

Question

Im tạo ứng dụng trong đó nhiều người dùng có thể đăng nhận xét bên trên hoặc bên dưới các nhận xét khác. Đây không phải là cấu trúc kiểu luồng. Nó giống như cộng tác trên một tài liệu Word. Im gặp sự cố khi thiết kế phương thức mà các mục này được sắp xếp.

Sử dụng mySQL và PHP, sắp xếp theo thời gian nhập không hoạt động và không sắp xếp theo vị trí nhận xét vì vị trí thay đổi nếu người dùng đăng trong các nhận xét khác. Tôi không muốn phải sắp xếp lại các vị trí nhận xét cho mỗi mục nhập mới (nếu có hàng nghìn mục nhập và hàng tá người dùng làm điều tương tự).

Cách tốt nhất để thiết kế điều này là gì?

Answer 1

Tôi chắc chắn sẽ đi theo thứ tự theo vị trí. Khi chèn, nó chỉ là một câu hỏi tăng tất cả các mục bên dưới nó - một truy vấn update duy nhất. Một tính năng quan trọng của việc thực hiện đó là nó xử lý đồng thời rất tốt; nếu có hai chèn đồng thời, bạn không quan tâm đến thứ tự gia tăng được thực hiện (nhưng bạn cần một pk không vị trí để không có khó chịu khi một chèn xảy ra ở trên bạn).

Cách khác là mô hình hóa nó làm cây, có nghĩa là bạn chỉ cần cập nhật các mục nhập bên dưới bạn trong nhánh. Nhưng nó sẽ là một tình huống hiếm hoi mà chi phí bảo trì là chính đáng. (Một sự thỏa hiệp là để mô hình là một cây liễu - bạn chia tổng số thành các khối tạo thành các nhánh, nhưng bạn không cho phép các chi nhánh từ các chi nhánh, tránh phải cập nhật từng bản ghi, tuy nhiên tôi vẫn đoán nó không đáng giá so với phương pháp đầu tiên.)

Answer 2

Điều bạn mô tả là linked list. Vấn đề là chúng thường khó truy xuất chỉ bằng SQL. Giải pháp của tôi là sử dụng PHP để thực hiện sắp xếp khi truy xuất.

bảng của bạn sẽ giống như thế này:

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 
} 

truy vấn của bạn rất đơn giản:

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

Bước quan trọng là để xoa bóp các kết quả từ mysql_fetch_assoc() vào một mảng được lập chỉ mục theo để comment_id:

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

Kết quả trong một mảng tương tự như sau:

$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)); 

Chức năng PHP để sắp xếp chúng vào nề nếp thể hiển thị rất đơn giản:

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; 
} 

Bạn nhận được first_comment_id từ bảng trang. Tất nhiên, bạn vẫn phải thực hiện các chức năng để chèn một nút và xóa một nút, nhưng những người còn lại là bài tập cho người đọc. Đừng quên sử dụng các giao dịch để chèn và xóa các nút.

Thông tin thêm về danh sách liên kết trong 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

Answer 3

này nghe có vẻ giống như một thời điểm tốt để sử dụng MPTT, Modified Pre -Màu Traversa cây l. Nó thường được sử dụng cho các bảng bình luận luồng và những thứ có tính chất đó. Trong tất cả các cách để giữ cấu trúc phân cấp trong một RDBMS, nó có chi phí thấp nhất khi cắt tỉa hoặc thêm các nút vào cây.

đây là good intro, and another. Googling xung quanh cho nó sẽ giúp bạn có thêm một số thông tin. Nó không khó để thực hiện ở tất cả một khi bạn hiểu khái niệm.