如何在SQL中表示并插入有序列表？

Question

如何在SQL中表示并插入有序列表？

22

我想要在SQL表中表示列表 "hi", "hello", "goodbye", "good day", "howdy"（按照这个顺序）:

pk | i | val
------------
1  | 0 | hi
0  | 2 | hello
2  | 3 | goodbye
3  | 4 | good day
5  | 6 | howdy

'pk'是主键列。忽略它的值。

'i'是“索引”，用于定义'val'列中数值的顺序。它仅用于确定顺序，而数值本身并不重要。

我遇到的问题是在保持顺序的同时向列表中插入值。例如，如果我想插入"hey"，并且希望它出现在"hello"和"goodbye"之间，那么我必须移动"goodbye"和"good day"的'i'值（但最好不要移动"howdy"）以为新条目腾出位置。

那么，是否有一种标准的SQL模式来执行移位操作，但只移动必要的元素？（请注意，简单的“UPDATE table SET i=i+1 WHERE i>=3”不起作用，因为它违反了' i '上的唯一性约束，并且还不必要地更新了“howdy”行。）

或者，有没有更好的方法来表示有序列表？我想你可以将'i'设置为浮点值，并选择介于值之间的值，但那么你必须有一个单独的重新平衡操作，当不存在这样的值时。

还是有标准的算法可以生成任意其他字符串之间的字符串值，如果我将'i'作为varchar？

还是我应该将其表示为链表？我之所以避免这样做，是因为我希望也能够执行SELECT..ORDER BY以按顺序获取所有元素。

- Travis

1

可能是更新列表中的内容而不必访问每个条目的重复问题。 - Michael Mrozek

2

顺便提一下，你的评论“UPDATE table SET i=i+1 WHERE i>=3”不起作用，因为它违反了“i”的唯一性约束，这绝对不适用于SQL Server。约束在最后检查。你使用的是什么RDBMS？ - Martin Smith

4个回答

4

如果您使用字符串而不是数字，您可能会有一个表格：

pk | i | val
------------
1  | a0 | hi
0  | a2 | hello
2  | a3 | goodbye
3  | b  | good day
5  | b1 | howdy

您可以在a3和b之间插入a4，在a2和a3之间插入a21，在a0和a2之间插入a1等。您需要一个聪明的函数来为新值v在p和n之间生成i，索引可能变得越来越长，或者您需要定期进行大规模的重新平衡。

另一种方法是在表中实现（双）链表，其中不保存索引，而是保存到前一个和后一个的链接，这意味着通常只需更新1-2个元素。

pk | prev | val
------------
1  |   0  | hi
0  |   1  | hello
2  |   0  | goodbye
3  |   2  | good day
5  |   3  | howdy

你好，介于打招呼和告别之间：

"hey" 获得了一个 pk 6。

pk | prev | val
------------
1  |   0  | hi
0  |   1  | hello 
6  |   0  | hi <- ins
2  |   6  | goodbye <- upd
3  |   2  | good day
5  |   3  | howdy

前一个元素将是pk=0的hello，而连接到hello的goodbye现在必须在未来链接到hey。

但我不知道是否有可能为许多数据库实现找到“order by”机制。

- user unknown

使用字符串是很可怕的（但相当聪明）。甚至可能很快；如果在i列上建立索引，有序查询应该很便宜，并且由于数据局部性，可能比链表方法具有优势。 - David Given

3

通过使用级联触发器，您可以轻松实现此操作。在插入/更新操作中，将任何“索引”条目更新为新条目的值，并使其等于索引值+1。这将通过所有行进行级联，直到第一个间隙停止级联——请参见这篇博客文章中的第二个示例，了解PostgreSQL实现。

只要RDBMS支持在更新/插入之前触发触发器，此方法就应该适用于所有RDBMS。它基本上做的是，如果您在代码中实现所需的行为（增加所有后续索引值，直到遇到间隙），但方式更简单、更有效。

或者，如果您可以接受对SQL Server的限制，请检查层次结构类型。虽然主要用于定义嵌套层次结构，但也可用于平面排序。它有点像您使用浮点数的方法，因为它允许通过指定分数值在两个位置之间插入数据，从而避免了更新其他条目的需要。

- Henrik Opel

1

我正在使用SQLite，显然它不支持级联/递归触发器（尽管它支持“before”触发器）。 - Travis

2

@Travis：看起来从3.6.18版本开始，他们增加了对递归触发器的支持，但你必须显式地打开它：http://www.sqlite.org/pragma.html#pragma_recursive_triggers - 不过我不确定在你的情况中'cascade'是否算作递归，因为它永远不会影响插入/更新的行本身，而总是影响其他行，所以尝试一下也许是值得的。 - Henrik Opel

1

谢谢，我没看到那个。不过，递归深度有一个编译内置的上限（默认为1000），我不知道它是否能处理非常高的值，这可能会成为我的问题。最终我决定取消对“i”的唯一性约束，并暂时使用“i=i+1 WHERE i>=new_i”的方法。如果更新额外的“i”值实际上变成了性能问题，我将重新审视这个决定。 - Travis

0

由于我曾遇到过类似的问题，这里提供一个非常简单的解决方案：

将你的 i 列设置为浮点数，但在初始数据中插入整数值：

pk | i   | val
------------
1  | 0.0 | hi
0  | 2.0 | hello
2  | 3.0 | goodbye
3  | 4.0 | good day
5  | 6.0 | howdy

然后，如果你想在两个值之间插入一些东西，只需计算出这两个相邻值的中间浮点数：

pk | i   | val
------------
1  | 0.0 | hi
0  | 2.0 | hello
2  | 3.0 | goodbye
3  | 4.0 | good day
5  | 6.0 | howdy
6  | 2.5 | hey

这种方式在相同两个值之间插入的次数受到浮点数精度的限制，但对于几乎所有情况来说，这应该已经足够了。

- sonovice

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Randy · Accepted Answer

当我阅读您的帖子时，一直在想“链表”，最终仍然认为这是正确的方法。

如果您正在使用Oracle，并且链表是一个单独的表（甚至是同一个表，具有自引用ID - 我会避免这种情况），那么您可以使用CONNECT BY查询和伪列LEVEL来确定排序顺序。