RDBMS中有序列表最合适的数据结构？

Question

我在MySQL数据库中存储了数百万项的有序列表.通常,需要在列表中添加或删除项目; 同样经常,必须确定项目列表中的位置.我会说读/写比率大约是50:50.

从链表模型开始,我阅读[1]和那里讨论的各种模型.对于严格的链表,邻接列表模型可以正常工作,但由于读/写比率或多或少相等,我采用标准连续列表进行分而治之:

将整个列表划分为近似长度的"桶"(比如~10000),保持桶大小的索引及其在主列表中的相对位置.每个项目都分配给一个特定的存储桶,并跟踪其在该存储桶中的位置.

通过这种方法,项目的位置是通过将列表中项目桶之前的桶的大小相加,然后在其自己的桶中添加项目的位置来确定的.要从列表中插入/删除项目,结果项目的"移位"将本地化到要添加或删除项目的存储区; 该桶的大小也必须相应更新.

在这种方法中存在一些非规范化(桶大小),即使对于事务,它也不具有本质上的线程安全性,因为在删除/插入期间必须查询项目表以确定要修改的项目的桶位置,然后更新以对该项目的存储桶中的所有其他项执行"移位".除非这些操作是原子的(通过存储过程可能？)线程始终是死锁.

是否有更复杂的方法将这种数据保存在RDBMS中？线程安全问题让我头痛不已,感觉应该有更好的方法来解决这个问题,而不是强迫我使用存储过程.

非常感谢,马特.

[1] 树数据结构的数据库结构

Answer 1

如果您需要一个链表（而不是层次结构），您可以使用我博客中这篇文章中描述的方法：

• 排序列表

，通过这个简单的查询：

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