用于管理有序列表的功能和模式

Question

我在应用程序设计中有一个常见的场景，我需要存储一个有序列表，并通过应用程序 UI 轻松访问和调整排序。

排序操作很简单，在一个时间上只有一个项目操作-移动到顶部，移至底部，移动了一个位置，或者下一个位置。这些定位操作可能穿插在典型的添加/编辑/删除列表操作中。为了讨论，这是一个单用户应用程序和数据库存储。

因为对象可能非常复杂，我想避免缓存整个列表客户端，并在内存中跟踪新创建的对象，直到发生大的保存操作。

我几乎只在这些项目中使用 MS-SQL，我想知道是否应该使用数据库功能、SQL 功能或设计模式来更好地支持有序列表的管理。

我目前的方法是使用一DECIMAL列来存储列表位置，这些位置在项目移动过程中变为小数。然后我对列表进行排序并重新生成整数位置以规范化列表。在此操作之后，它已准备好进行另一项移动。

在示例实现中，我创建了一个名为Seq位置跟踪的列。一次小数位足以用于 0.5 存储。

[Seq] [decimal](10, 1) NOT NULL

当一个项目在应用程序 UI 中重新定位时，

1. 我UPDATE用新的Seq价值记录
2. 我检索完整表，按升序排序Seq并Seq从基于 1 的整数系列重新生成表中的所有值

新Seq值很容易计算-

• 移到顶部 = 0
• 移到底部 = MAX(Seq) + 1
• 上移 = 从当前 Seq 值中减去 1.5
• 下移 = 当前 Seq 值加 1.5

随着列表变长，更新变慢，因为我正在执行 N 个UPDATE语句，其中 N 是表中的行数，因此它似乎只适用于小表。

• 是否有某种内置功能来管理 SQL 或 MS-SQL 中的有序列表？
• 有没有办法在一次调用中更新多行？

一种更高效的方法是允许更多的小数位，然后定位在两个相邻项目的中间位置，在列表上没有重新排序。

• 移到顶部 = Min(Seq) - 1
• 移到底部 = MAX(Seq) + 1
• 上移 = 前 2 个项目 Seq 值的中位数
• 下移 = 后面 2 个项目 Seq 值的中位数

这种方法只需要一个SELECT（最多包含 2 行）和一个UPDATE.

但是，如果有足够的重新定位，我想该字段会用完小数位。例如，如果我从位置 10 和 11 处的项目开始，并从位置 9 继续向下移动列表中的项目，它们将被赋予 10.5、10.25、10.125 的序列。10 次移动后，仓位变长... 10.0009765625。

更新 #1 - 改进了列表的重新排序

对于重测序，我更赶上上row_number()，OVER和WITH在MS-SQL的功能。很高兴发现有一种更流畅的方法可以在单个UPDATE操作中重新排序列表；

with OrderedItems as 
(
    select
        ItemID,
        Seq,
        row_number() over (order by Seq asc) NewSeq
    from 
        Items
)
update OrderedItems
set Seq = NewSeq

Answer 1

最后一种是经常使用的技术，而且很有效。如果您担心用完小数位，您可以对其进行改进，以检测下两个前一个/后一个值之间的平均值何时无法与其中之一区分开（即：您用完了小数位）。

发生这种情况时，您应该根据需要向上或向下重新排序尽可能多的行。

假设您只使用 2 位小数，并且有两行分别为Seq1.00 和 1.01；下一个值为 2.00。如果您想使用您的技术在这两者之间移动一行，则Seq= (1.00, 1.005 , 1.01, 2.00)。这将需要比可用的小数更多的位数，并且根据舍入规则，1.005 将舍入为 1.00 或 1.01。在任何情况下，您都可以检测到插入的值与 1.00 或 1.01 无法区分。

在这种情况下，您需要“向下（或向上）推并腾出空间”。也就是说，您应该再更改一行，并得到 (1.00, 1.25, 1.50 , 2.00)。您已将更改分散到两行，而不是仅仅一行。

如果您遇到诸如 (1.01, 1.02, 1.03, 1.04, ...) 之类的情况，这可能需要递归（或迭代）地完成。

通过对原始技术的扩展，您无需重新规范化。这仅在“根据需要”的基础上进行处理，并且可以很好地扩展。

笔记：

1. 实现该算法可能有点棘手，因为您需要考虑何时位于第一行或最后一行，以及如何处理这些，以及数字何时Seq达到最大或最小可用值。

2. 该算法适用于任意数量的小数，包括 0。也就是说，您也可以将它与整数值一起使用decimal，而不是 ，这可能会证明计算效率更高，或者根据decimals实现方式，也可以提高空间效率。