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

Question

我正在使用 Django 和 PostgreSQL，但如果有更好的方法使用原始 SQL 或特定于数据库的操作来执行此操作，我并不绝对依赖 Django ORM。

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

(operation on A, with subset B, C, E)A -> BB -> CC -> ED -> DE -> ANotice how D does not move.

In general, the subset of items will not be more than about 50 items, but the base list may grow to tens of thousands of entries.

The most obvious way of implementing this is with a simple integer order field. This seems suboptimal. It requires the compromise of making the position ordering column non-unique, where non-uniqueness is only required for the duration of a modification operation. To see this, imagine the minimal operation using A with subset B:

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

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

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

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

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

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

我考虑过的另一种结构是链表(和变体)。这具有直接修改的优点，但我不确定它相对于 SQL 的属性 - 在 SQL 查询中排序这样的列表似乎很痛苦，并且提取列表的非顺序子集非常糟糕检索属性。

除此之外，还有B-Trees，各种二叉树等等。你对这个数据结构有什么建议？ SQL 中是否有针对此解决方案的标准数据结构？使用连续整数的最初想法真的会出现缩放问题，还是我看到了没有问题的地方？

Answer 1

首选解决方案:

A linked list将是实现这一目标的通常方法。按顺序返回项目的查询是 trivial in Oracle ，但我不确定您将如何在 PostreSQL 中执行此操作。

另一种选择是使用 ltree module for postgresql. 来实现它

不太优雅(和写入繁重)的解决方案:开始交易。行级锁范围内的“选择更新”。将目标记录移动到位置 0，将目标 future 的后续记录更新为 +1，其中它们的位置高于目标原始位置(反之亦然)，然后将目标更新到新位置 - 无需进行一次额外的写入一个独特的约束。提交:D

如果您可以等待 Postgresql 8.5(Alpha 可用)，这是一个简单(但仍然需要大量写入)的解决方案:)

将其包装在事务中，在范围内选择更新，并使用延迟约束(postgresql 8.5 has support for deferred unique constraints，如 Oracle)。