algorithm - 同步两个有序列表

Question

我们有两个通常无法相互通信的离线系统。两个系统都维护相同的有序项目列表。他们很少能够相互通信以同步列表。

项目标有修改时间戳以检测编辑。项目由 UUID 标识，以避免在插入新项目时发生冲突(与使用自动递增整数相反)。同步时会检测到新的 UUID 并将其复制到其他系统。同样对于删除。

上面的数据结构对于无序列表来说没问题，但是我们如何处理排序呢？如果我们添加一个整数“等级”，则在插入新项目时需要重新编号(因此需要同步所有后继项目，因为只有 1 次插入)。或者，我们可以使用小数等级(使用前项和后项的等级的平均值)，但这似乎不是一个可靠的解决方案，因为当插入许多新项时它会很快遇到准确性问题。

我们还考虑将其实现为双向链表，其中每个项目都包含其前项和后项的 UUID。但是，这仍然需要在插入 1 个新项目时同步 3 个项目(或者在删除 1 个项目时同步剩余的 2 个项目)。

我们最好使用一种数据结构或算法，其中只有新插入的项目需要同步。是否存在这样的数据结构？

编辑:我们也需要能够处理将现有项目移动到不同位置的问题!

Answer 1

插值排名方法确实没有问题。只需根据表示 0 和 1 之间没有尾随零的二进制小数的可变长度位向量定义您自己的编号系统。二进制小数点在第一个数字的左边。

该系统唯一的不便之处在于空位向量给出的最小可能 key 为 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)和111相加得到1.001，然后移位得到 1001。这作为插值很好用。但请注意，最后的 1 不必要地使其比任何一个操作数都长。一个简单的优化是删除最后的 1 位和尾随零以得到简单的 1。果然，1 大约是我们希望的一半。

当然，如果您在同一位置进行多次插入(例如，考虑在列表开头连续插入)，位向量会变长。这与在二叉树中的同一点插入完全相同的现象。它长得又长又细。要解决此问题，您必须在同步期间通过使用尽可能短的位向量重新编号来“重新平衡”，例如对于 14，您将使用上面的序列。

添加

虽然我还没有尝试过，但 Postgres bit string type似乎足以满足我所描述的键。我需要验证的是整理顺序是否正确。

此外，对于任何 k>=2 的以 k 为底的数字，同样的推理也适用。第一项获得 key k/2。还有一个简单的优化可以防止非常常见的分别在末尾和前面追加和前置元素的情况导致长度为 O(n) 的键。它为这些情况维护 O(log n)(尽管在内部相同的位置插入仍然可以在 p 插入后生成 O(p) 键)。我会让你解决这个问题。当 k=256 时，您可以使用无限长的字节串。在 SQL 中，我相信您会想要 varbinary(max)。 SQL 提供正确的词典排序顺序。如果您有一个类似于 Java 的 BigInteger 包，则插值操作的实现很容易。如果您喜欢人类可读的数据，您可以将字节字符串转换为例如十六进制字符串 (0-9a-f) 并存储它们。那么正常的UTF8字符串排序顺序是正确的。