我使用的是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中有标准的数据结构吗?使用顺序整数的最初想法是真的会有缩放问题,还是我看到了没有问题的问题?
在我看来,您真正的问题是需要在事务期间锁定表。我不认为一次操作就可以解决这个问题,因此需要锁定。
所以问题是,您是否可以用“Django方式”而不是直接使用SQL来实现这一点。搜索“django lock table”会发现一些有趣的链接,包括this snippet,还有许多其他链接实现了类似的行为。
在这个stack overflow post中可以找到一个直接的SQL链表样式的解决方案,在我看来它是逻辑的和简洁的,但它又是两个操作。
我很想知道结果如何,你的最终解决方案是什么,一定要让我们更新!
临时表和事务应保持原子性和排序顺序的唯一约束。要重新说明问题,请从以下位置开始:
每行之间可以有任意数量的项。所以,首先读入记录并创建一个列表
[['A',10],['B',25],['C',26],['E',34]]
。通过一些pythonic魔术,您可以移动标识符并将其插入临时表中:现在更新:
我只是假设pgsql可以处理这个查询。如果可以,它将是原子的。
可选地,将表REORDER创建为永久表,事务将确保两次对同一记录重新排序的尝试将被序列化。
编辑:有一些事务问题。你可能需要实现我的两个想法。如果两个进程都希望更新项B(例如),则可能会出现问题。因此,假设所有的顺序值都是偶数:
sort_order
字段甚至是某个其他进程添加了与您的条件匹配的记录,请选择您刚刚更新的数据。您可以中止事务并重新启动,也可以只使用在步骤2中更新的记录来删除记录并完成操作。要做的“正确”的事情取决于您需要这些代码来完成什么。步骤2确保如果两个列表重叠,则只有第一个列表可以访问行 在交易完成前存在疑问:
或者,可以向表中添加一个控件字段以获得相同的效果,然后不需要使用
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)。
相关问题 更多 >
编程相关推荐