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