36

我在数据库中有一组对象。照片库中的图像、目录中的产品、书中的章节等。每个对象都表示为一行。我希望能够任意排序这些图像，将该排序存储在数据库中，这样当我显示对象时，它们就会以正确的顺序排列。

例如，假设我正在写一本书，每一章都是一个对象。我写我的书，并按以下顺序排列章节：

简介、可访问性、形式与功能、错误、一致性、结论、索引

它转到编辑器，并返回以下建议的顺序：

介绍、形式、功能、可访问性、一致性、错误、结论、索引

如何以稳健、有效的方式将此排序存储在数据库中？

我有以下想法，但我对其中任何一个都不感到兴奋：

  1. 大批。每行都有一个排序 ID，当更改顺序时（通过删除后插入），订单 ID 会更新。这使得检索变得容易，因为它只是ORDER BY，但似乎很容易破解。

    // REMOVAL
    UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
    UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
    // INSERTION
    UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
    UPDATE ... SET orderID=insertionID WHERE ID=addedID

  2. 链表。每行都有一列用于排序中下一行的 id。遍历在这里似乎很昂贵，尽管可能通过某种方式使用ORDER BY我没有想到的。

  3. 间隔数组。将 orderingID（如 #1 中使用的）设置为大，所以第一个对象是 100，第二个是 200，依此类推。然后当插入发生时，您只需将其放在(objectBefore + objectAfter)/2. 当然，这需要偶尔重新平衡，所以你不会让事物靠得太近（即使使用浮点数，你最终也会遇到舍入错误）。

这些对我来说都不是特别优雅。有没有人有更好的方法来做到这一点？

4

11 回答 11

7

另一种选择是（如果您的 RDBMS 支持）使用数组类型的列。虽然这违反了规范化规则，但在这种情况下它可能很有用。我知道的一个具有数组的数据库是 PostgreSQL。

于 2008-08-22T05:32:46.497 回答
4

Rails 中的acts_as_list mixin 基本上按照您在#1 中概述的方式处理这个问题。它查找一个名为 position 的 INTEGER 列（当然，您可以覆盖它的名称）并使用它来执行 ORDER BY。当您想重新排序时，您会更新职位。每次我使用它时，它对我都有好处。

作为旁注，您可以通过使用稀疏编号来消除始终在 INSERTS/DELETES 上重新定位的需要——有点像过去的基本操作......您可以将您的位置编号为 10、20、30 等。如果您需要在 10 到 20 之间插入一些内容，您只需将其插入位置为 15。同样，在删除时您可以删除该行并留下间隙。仅当您实际更改订单或尝试插入并且没有适当的间隙可插入时，您才需要重新编号。

当然，根据您的特定情况（例如，您是否已经将其他行加载到内存中），使用间隙方法可能有意义，也可能没有意义。

于 2008-08-21T23:11:17.820 回答
3

如果对象没有被其他表大量键控，并且列表很短，那么删除域中的所有内容并重新插入正确的列表是最简单的。但是，如果列表很大并且您有很多限制来减慢删除速度，那么这是不切实际的。我认为您的第一种方法确实是最干净的。如果您在事务中运行它，您可以确保在更新过程中不会发生任何奇怪的事情以搞砸订单。

于 2008-08-22T01:39:15.390 回答
3

只是考虑选项 #1 与 #3的想法：间隔数组选项（#3）是否只会推迟普通数组（#1）的问题？无论您选择哪种算法，要么它已损坏，您稍后会遇到＃3 的问题，要么它可以工作，然后＃1 应该也能正常工作。

于 2008-08-25T17:24:13.627 回答
2

我在我的上一个项目中这样做了，但它是针对只偶尔需要专门订购的表，并且不经常访问。我认为间隔数组将是最好的选择，因为在平均情况下，它的重新排序是最便宜的，只涉及对一个值的更改和对两个值的查询）。

此外，我认为 ORDER BY 将由数据库供应商进行大量优化，因此与链表实现相比，利用该功能将有利于性能。

于 2008-08-22T01:58:14.423 回答
2

使用浮点数来表示每个项目的位置：

项目 1 -> 0.0

项目 2 -> 1.0

项目 3 -> 2.0

项目 4 -> 3.0

您可以通过简单的二分法将任何项目放置在任何其他两个项目之间：

项目 1 -> 0.0

项目 4 -> 0.5

项目 2 -> 1.0

项目 3 -> 2.0

（在项目 1 和项目 2 之间移动项目 4）。

由于浮点数在计算机系统中的编码方式，二分过程几乎可以无限期地继续。

项目 4 -> 0.5

项目 1 -> 0.75

项目 2 -> 1.0

项目 3 -> 2.0

（将第 1 项移动到第 4 项之后的位置）

于 2008-09-18T00:22:32.820 回答
2

由于我主要使用 Django 遇到此问题，因此我发现此解决方案是最可行的。在关系数据库中似乎没有任何“正确的方法”可以做到这一点。

于 2009-03-29T14:47:15.043 回答
1

我会做一个连续的数字，如果它已经存在，则在表上使用一个触发器“为优先级腾出空间”。

于 2008-08-21T23:12:30.123 回答
1

我也有这个问题。我承受着巨大的时间压力（不是我们所有人），我选择了选项＃1，并且只更新了更改的行。

如果您将第 1 项与第 10 项交换，只需执行两次更新以更新第 1 项和第 10 项的订单号。我知道这在算法上很简单，这是 O(n) 最坏的情况，但最坏的情况是当你有列表的总排列。这种情况多久会发生一次？那是你来回答的。

于 2008-09-18T00:34:31.777 回答
0

我遇到了同样的问题，并且可能至少花了一周的时间来考虑正确的数据建模，但我想我终于明白了。使用 PostgreSQL 中的数组数据类型，您可以存储每个订购项目的主键，并在订单更改时使用插入或删除相应地更新该数组。引用单行将允许您根据数组列中的顺序映射所有对象。

它仍然是一个有点不稳定的解决方案，但它可能会比选项 #1 工作得更好，因为选项 1 需要在订购更改时更新所有其他行的订单号。

于 2016-01-28T10:32:16.580 回答
0

方案#1 和方案#3 在除INSERT写入之外的每个操作中都具有相同的复杂性。方案#1 有 O(n) 次写入INSERT，方案#3 有 O(1) 次写入INSERT。

对于每个其他数据库操作，复杂性是相同的。

方案#2 甚至不应该被考虑，因为它DELETE需要 O(n) 读取和写入。方案 #1 和方案 #3DELETE的读取和写入都为 O(1)。

新方法

如果您的元素有一个不同的父元素（即它们共享一个外键行），那么您可以尝试以下...

Django 提供了一种与数据库无关的解决方案来在CharField(). 一个缺点是存储字符串的最大长度不能大于max_length，这取决于 DB。

就复杂性而言，这将使 Scheme #1 O(1) 写入INSERT，因为排序信息将作为单个字段存储在父元素的行中。

另一个缺点是JOIN现在需要到父行来更新排序。

https://docs.djangoproject.com/en/dev/ref/validators/#django.core.validators.validate_comma_separated_integer_list

于 2018-12-15T14:48:34.233 回答