6

我在 MySQL 数据库中存储了数百万个项目的有序列表。合理地经常需要从列表中添加或删除项目；同样，必须确定项目在列表中的位置。我会说读/写比率约为50:50。

从链表模型开始，我阅读了 [1] 以及那里讨论的各种模型。对于严格的链表，邻接表模型可以正常工作，但由于读/写比率或多或少相等，我采用了使用标准连续列表的分而治之的方法：

将整个列表分成近似长度的“桶”（比如~10000），维护桶大小的索引及其在主列表中的相对位置。每个项目都分配给特定的存储桶并跟踪其在该存储桶中的位置。

使用这种方法，项目的位置是通过将列表中项目存储桶之前的存储桶的大小相加来确定的，然后将项目的位置添加到它自己的存储桶中。要从列表中插入/删除项目，所产生的项目的“移动”被本地化到正在添加或删除项目的桶中；该存储桶的大小也必须相应更新。

这种方法有一些非规范化（桶大小），它本质上不是线程安全的，即使对于事务也是如此，因为在删除/插入期间，必须查询项目表以确定被修改项目的桶位置，然后更新以对该项目的存储桶中的所有其他项目执行“转移”。除非这些操作是原子的（可能是通过存储过程？）线程一直死锁。

有没有更合适的方法将此类数据保存在 RDBMS 中？线程安全问题让我很头疼，感觉应该有比强迫我使用存储过程更好的方法来解决这个问题。

非常感谢，马特。

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

4

1 回答 1

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
于 2009-06-25T10:54:41.550 回答