代码之家 › 专栏 › 技术社区 › tghw megawac

表示关系数据库中的顺序

django-models django database sql

tghw megawac · 技术社区 · 16 年前

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

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

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

它将转到编辑器,并返回以下建议顺序:

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

我如何以一种健壮、高效的方式将这个顺序存储在数据库中?

我有以下想法,但我对其中任何一个都不感兴趣:

数组。每一行都有一个排序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
链表。每一行都有一列作为排序中下一行的ID。遍历在这里似乎很昂贵,尽管可能有某种方法可以使用 按顺序 我没想过。
间隔阵列。将orderingID(如在1中所用)设置为大,因此第一个对象为100,第二个对象为200等。然后,当发生插入时,只需将其放置在 (objectBefore + objectAfter)/2 . 当然,这需要偶尔进行重新平衡,这样您就不会把事情过于紧密地联系在一起(即使有了浮动,最终也会遇到舍入错误)。

这些对我来说都不是特别优雅的。有人有更好的方法吗?

11 回复 | 直到 6 年前

Grey Panther 16 年前

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

John 16 年前

在Rails中,acts_as_list mixin基本上按照您在1中概述的方式来处理。它查找一个名为position的整型列(当然可以覆盖到name),并使用该列进行排序。当你想重新订购东西时,你会更新位置。每次我用它都很好。

作为一个补充说明,您可以通过使用稀疏编号来消除总是重新定位插入/删除的需要——类似于当天的基本编号……你可以给你的位置编号10、20、30等等,如果你需要在10到20之间插入一些东西,你只需要在15之间插入。同样,删除时,只需删除行并留出间隙。您只需要在实际更改顺序或尝试执行插入操作且没有适当的插入间隔时重新编号。

当然,根据您的特定情况(例如,是否已将其他行加载到内存中),使用GAP方法可能有意义,也可能没有意义。

onnodb 16 年前

只是考虑一下 选项1与Vx 3 :间隔数组选项(3)是否只会推迟正常数组(1)的问题?无论你选择哪种算法,要么它坏了,你会在3以后遇到问题,要么它能工作,然后1也能工作。

Eric Z Beard 16 年前

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

pbh101 16 年前

我在上一个项目中这样做了,但这是为一个表而做的,只是偶尔需要特定的排序,而且访问频率不太高。我认为间隔数组是最好的选择,因为它的重新排序在一般情况下是最便宜的,只需要更改一个值和查询两个值)。

另外,我认为ORDERBY将被数据库供应商大量优化,因此利用该功能将有利于性能,而不是链表实现。

Seun Osewa 16 年前

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

项目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之后的位置)

Stu 16 年前

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

moffdub 16 年前

我也有这个问题。我面临着巨大的时间压力(不是所有人),我选择了选项1,只更新了更改过的行。

如果将项目1与项目10交换,只需进行两次更新即可更新项目1和项目10的订单号。我知道它在算法上很简单,而且它是O(N)最坏的情况,但是最坏的情况是当你有一个列表的全部排列时。多久会发生一次?那是你的答案。

tghw megawac 16 年前

因为我经常和Django碰上这个,我发现 this solution 是最可行的。在关系数据库中似乎没有任何“正确的方法”可以做到这一点。

Austin T 9 年前

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

解决方案仍然有点复杂,但可能比选项1更好,因为选项1要求在排序更改时更新所有其他行的订单号。

Chris Conlan 6 年前

方案1和方案3在每个操作中具有相同的复杂性,除了 INSERT 写。方案1上有O(N)个写入 插入 方案3上有O(1)个字 插入 .

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

方案2甚至不应考虑,因为 DELETE 需要O(N)读写。方案1和方案3有O(1) 删除 用于读写。

新方法

如果您的元素有一个独特的父元素(即它们共享一个外键行),那么您可以尝试以下操作…

Django提供了一个数据库不可知的解决方案,用于存储整数列表 CharField() . 一个缺点是存储字符串的最大长度不能大于 max_length ,这取决于数据库。

就复杂性而言,这将使方案为 插入 ,因为排序信息将作为单个字段存储在父元素的行中。

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

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