用于存储排序字段以有效允许修改的数据结构

2024-03-28 20:36:07 发布

您现在位置:Python中文网/ 问答频道 /正文

我使用的是Django和PostgreSQL,但是如果有更好的方法来处理原始SQL或数据库特定的操作,我并不完全依赖于Django or m。

我有一个需要顺序排序的模型。查找操作通常会按顺序检索整个列表。此数据上最常见的操作是将行移动到列表的底部,中间项的子集将冒泡起来,以替换前面的项,如下所示:

(operation on A, with subset B, C, E)

A -> B
B -> C
C -> E
D -> D
E -> A

Notice how D does not move.

一般来说,项目的子集不会超过50个项目,但是基本列表可能会增加到数万个条目。

最明显的实现方法是使用一个简单的整数顺序字段。这似乎不太理想。它要求将位置排序列设为非唯一列,其中仅在修改操作期间才需要非唯一性。要了解这一点,请想象使用A和子集B的最小操作:

oldpos = B.pos
B.pos = A.pos
A.pos = oldpos

即使您已经存储了位置,但在第二行您违反了唯一性约束。此外,这种方法会使原子性产生问题——读操作必须在写之前进行,在此期间,记录可能会发生更改。Django的默认事务处理文档没有解决这个问题,尽管我知道在SQL中应该可以使用事务锁定的“可重复读取”级别。

我正在寻找更适合这种使用模式的替代数据结构。我看了this question找主意。

有一个建议是杜威十进制的解决方案,它使插入操作在现有值之间以数字形式出现,因此在B和C之间插入A会导致:

A=1   ->   B=2
B=2   ->   A=2.5
C=3   ->   C=3

这解决了列唯一性问题,但引入了列必须是指定小数位数的浮点的问题。要么我估计过高,存储的数据比我需要的要多得多,要么系统会受到我施加的任意小数长度的限制。此外,我不希望使用超过数据库-一些键将比其他键移动得更频繁,使此解决方案更快达到极限。我可以通过周期性地对数据库重新编号来解决这个问题,但是一个好的数据结构似乎应该避免需要这样做。

我考虑过的另一个结构是链表(和变体)。这样做的好处是可以直接进行修改,但我不确定它与SQL有关的属性—在SQL查询中对这样一个列表排序似乎很痛苦,而且提取列表的非顺序子集具有糟糕的检索属性。

除此之外,还有B-树、各种二叉树等等。对于这种数据结构,您有什么建议?这个解决方案在SQL中有标准的数据结构吗?使用顺序整数的最初想法是真的会有缩放问题,还是我看到了没有问题的问题?


Tags: 数据项目django方法pos数据库数据结构列表
3条回答

在我看来,您真正的问题是需要在事务期间锁定表。我不认为一次操作就可以解决这个问题,因此需要锁定。

所以问题是,您是否可以用“Django方式”而不是直接使用SQL来实现这一点。搜索“django lock table”会发现一些有趣的链接,包括this snippet,还有许多其他链接实现了类似的行为。

在这个stack overflow post中可以找到一个直接的SQL链表样式的解决方案,在我看来它是逻辑的和简洁的,但它又是两个操作。

我很想知道结果如何,你的最终解决方案是什么,一定要让我们更新!

临时表和事务应保持原子性和排序顺序的唯一约束。要重新说明问题,请从以下位置开始:

A  10   to  B  10
B  25       C  25
C  26       E  26
E  34       A  34

每行之间可以有任意数量的项。所以,首先读入记录并创建一个列表[['A',10],['B',25],['C',26],['E',34]]。通过一些pythonic魔术,您可以移动标识符并将其插入临时表中:

create temporary table reorder (
    id varchar(20), -- whatever
    sort_order number,
    primary key (id));

现在更新:

update table XYZ
set sort_order = (select sort_order from reorder where xyz.id = reorder.id)
where id in (select id from reorder)

我只是假设pgsql可以处理这个查询。如果可以,它将是原子的。

可选地,将表REORDER创建为永久表,事务将确保两次对同一记录重新排序的尝试将被序列化。


编辑:有一些事务问题。你可能需要实现我的两个想法。如果两个进程都希望更新项B(例如),则可能会出现问题。因此,假设所有的顺序值都是偶数:

  1. 开始交易
  2. 增加1正在使用的所有订单。这将对要更新的所有行设置行级写锁。
  3. 如果任何sort_order字段甚至是某个其他进程添加了与您的条件匹配的记录,请选择您刚刚更新的数据。您可以中止事务并重新启动,也可以只使用在步骤2中更新的记录来删除记录并完成操作。要做的“正确”的事情取决于您需要这些代码来完成什么。
  4. 使用正确的偶数排序顺序填写上述临时重新排序表。
  5. 如上所述更新主表。
  6. 放下临时表。
  7. 提交事务

步骤2确保如果两个列表重叠,则只有第一个列表可以访问行 在交易完成前存在疑问:

update XYZ set sort_order = sort_order + 1
where -- whatever your select criteria are

select * from XYZ
where -- same select criteria
order by sort_order

或者,可以向表中添加一个控件字段以获得相同的效果,然后不需要使用sort_order字段。使用sort_order字段的好处是,当字段通常为空时,使用位字段或LOCK_BY_USERID字段进行索引往往性能较差,因为索引99%的时间没有意义。SQL引擎不喜欢大部分时间都是空的索引。

首选解决方案:

一个linked list将是实现这一目标的常用方法。按顺序返回项的查询是trivial in Oracle,但我不确定在PostreSQL中如何执行。

另一个选择是使用ltree module for postgresql.实现这个

不太优雅(而且写得很重)的解决方案: 启动事务。“在行级锁的作用域内选择“更新”。将目标记录移动到位置0,将目标未来的后续记录更新到位置高于目标原始位置(或相反)的+1,然后将目标更新到新位置-无唯一约束所需的单个附加重写。提交:D

如果您可以等待Postgresql 8.5(Alpha可用),则可以使用简单(但仍然编写繁重)的解决方案:)

将其包装在事务中,选择在作用域中更新,并使用延迟约束(postgresql 8.5 has support for deferred unique constraints类似于Oracle)。

相关问题 更多 >