同步两个有序列表

Question

我们有两个通常无法相互通信的离线系统.两个系统都保持相同的有序项目列表.他们很少能够彼此通信以同步列表.

项目标有修改时间戳以检测编辑.项目由UUID标识,以避免在插入新项目时发生冲突(与使用自动递增整数相反).检测到同步新UUID并将其复制到另一个系统时.删除也是如此.

上述数据结构适用于无序列表,但我们如何处理排序？如果我们添加整数"rank",那么在插入新项目时需要重新编号(因此需要同步所有后继项目,因为只有1次插入).或者,我们可以使用小数排名(使用前一项和后继项的排名的平均值),但这似乎不是一个强大的解决方案,因为当插入许多新项时,它会很快遇到准确性问题.

我们还考虑将其作为双重链接列表实现,每个项目都包含其前任和后续项目的UUID.但是,当插入1个新项目时,仍需要同步3个项目(或者当删除1个项目时同步2个剩余项目).

优选地,我们想要使用仅需要同步新插入的项的数据结构或算法.这样的数据结构是否存在？

编辑:我们需要能够处理将现有项目移动到其他位置!

Answer 1

插值秩方法确实没有问题。只需基于可变长度的位向量定义自己的编号系统，该向量表示0到1之间的二进制分数且没有尾随零。二进制点在第一个数字的左侧。

该系统的唯一不便之处在于，由空位向量给定的最小可能密钥为0。因此，仅当您肯定关联的项目将永远成为第一个列表元素时，才使用此选项。通常，只需将第一项设置为键1即可。它等于1/2，因此（0..1）范围内的随机插入将使位使用率降至最低。要在项目前后插值，

01 < newly interpolated = 1/4
1
11 < newly interpolated = 3/4

要再次插值：

001 < newly interpolated = 1/8
01
011 < newly interpolated = 3/8
1
101 < newly interpolated = 5/8
11 
111  < newly interpolated = 7/8

请注意，如果您愿意，可以省略存储最后的1个！所有密钥（除了您通常不会使用的0）都以1结尾，因此可以存储所有密钥。

二进制分数的比较与词法比较很像：0 <1，并且从左向右扫描的第一个位差告诉您哪个比较小。如果没有差异出现，即一个向量是另一个的严格前缀，则较短的向量较小。

有了这些规则，提出一个可以接受两个位向量并计算大致（或在某些情况下）它们之间的结果的算法非常简单。只需添加位串，然后右移1，删除不必要的尾随位，即取两者的平均值即可在范围之间进行划分。

在上面的示例中，如果删除导致我们：

01
111

并且我们需要对它们进行插值，将01(0)and与and 111获得1.001，然后转移为get 1001。作为插值，这很好用。但是请注意，最后一个1不必要地使它比两个操作数都更长。一种简单的优化方法是将最后1一位与尾随的零一起删除，以得到简单的1。果然，1大约是我们希望的一半。

当然，如果您在同一位置进行多次插入（例如，在列表的开头考虑连续插入），则位向量将变长。这与在二叉树的同一点插入相同的现象。它长而坚硬。为了解决这个问题，您必须在同步期间通过使用尽可能短的位向量重新编号来“重新平衡”，例如对于14，您将使用上面的序列。

加成

尽管我还没有尝试过，但是Postgres 位字符串类型似乎足以满足我所描述的键。我需要验证的是排序顺序正确。

同样，对于任何，以k为基数的数字都可以进行相同的推理k>=2。第一项得到key k/2。还有一个简单的优化，可以防止在结尾处和前面分别添加和前置元素的非常常见的情况导致键长度为O（n）。在这种情况下，它保持O（log n）（尽管在内部插入同一位置在p插入后仍可以产生O（p）密钥）。我会让你解决。如果k = 256，则可以使用不定长度的字节字符串。在SQL中，我相信您想要与Java类似的软件包。如果您喜欢人类可读的数据，则可以将字节字符串转换为例如十六进制字符串（0-9a-f）并进行存储。那么正常的UTF8字符串排序顺序是正确的。varbinary(max)。SQL提供了正确的字典编排顺序。如果您有一个插值运算，则实现插值运算很容易BigInteger

Answer 2

您可以向每个项目添加两个字段 -“创建时间戳”和“插入时间”（包含在其后插入新项目的项目 ID）。同步列表后，发送所有新项目。这些信息足以让您能够在另一端构建列表。

收到新添加的项目列表后，执行以下操作（在接收端）：按创建时间戳排序，然后一项一项地进行排序，并使用“插入后”字段将新项目添加到适当的位置。

如果添加项目 A，然后在 A 之后添加 B，然后删除 A，您可能会遇到麻烦。如果发生这种情况，您还需要同步 A（基本上同步自上次同步以来列表上发生的操作，而不仅仅是当前列表的内容）。它基本上是日志传送的一种形式。