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

Question

我使用的是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中有标准的数据结构吗？使用顺序整数的最初想法是真的会有缩放问题，还是我看到了没有问题的问题？

Answer 1

首选解决方案：

一个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）。