RDBMS中有序列表的最合適的數據結構？

Question

我正在MySQL數據庫中存儲數百萬項的有序列表。通常情況下，項目需要添加或從列表中刪除;同樣經常，項目列表中的位置必須確定。我認爲讀寫比例大約是50:50。

從一個鏈表模型開始，我讀了[1]和在那裏討論的各種模型。對於一個嚴格的鏈表來說，鄰接表模型可以正常工作，但由於讀寫比率大致相等，我採用了標準連續列表的分而治之的方法：

劃分整個列表轉換成近似長度（比如〜10000）的「桶」，維護桶大小的索引及其在主列表中的相對位置。每個項目都分配給特定的存儲桶並跟蹤其在該存儲桶中的位置。

通過這種方法，物品的位置是通過累加列表中項目的存儲桶之前的存儲桶的大小，然後在自己的存儲桶中添加項目的位置來確定的。爲了從列表中插入/移除項目，結果項目的「移位」被本地化到正添加或移除項目的桶中;該桶的大小也必須相應更新。

這種方法存在一些非規範化（桶大小），即使對於事務也不是線程安全的，因爲在刪除/插入時必須查詢項目表以確定桶的位置物品被修改，然後更新以對該物品的所有其他物品執行「轉移」。除非這些行爲是原子的（通過存儲過程也許？）線程始終發生死鎖。

是否有更多適當的方法來將這類數據保存在RDBMS中？線程安全問題讓我頭痛不已，感覺應該有更好的方法來解決這個問題，而不是強迫我使用存儲過程。

非常感謝， 馬特。

[1] Database Structure for Tree Data Structure

Answer 1

如果你需要一個鏈表（不是一個層次），你可以使用這篇文章在我的博客中描述的方法：

• Sorting lists

，用這個簡單的查詢：

SELECT @r AS _parent, 
     @r := (
     SELECT id 
     FROM t_list 
     WHERE parent = _parent 
     ) AS id 
FROM (
     SELECT @r := 0 
     ) vars, 
     t_list 

確保您的id和parent的UNIQUE索引已定義爲有效。

將@r := 0替換爲@r := @id_of_record_to_start_with以開始從任何給定的id進行瀏覽。

要找出項目的位置，只是扭轉查詢：

SELECT COUNT(*) 
FROM (
     SELECT @r AS _id, 
       @r := (
       SELECT parent 
       FROM t_list 
       WHERE id = _id 
       ) AS id 
     FROM (
       SELECT @r := @item_id 
       ) vars, 
       t_list 
     ) q