我们有两个通常无法相互通信的离线系统。两个系统都维护相同的有序项目列表。他们很少能够相互通信以同步列表。
项目标有修改时间戳以检测编辑。项目由 UUID 标识，以避免在插入新项目时发生冲突（与使用自动递增整数相反）。同步时检测到新的 UUID 并将其复制到其他系统。对于删除也是如此。
上面的数据结构对于无序列表来说很好，但是我们如何处理排序呢？如果我们添加一个整数“等级”，则在插入新项目时需要重新编号（因此需要同步所有后续项目，因为只有 1 次插入）。或者，我们可以使用分数等级（使用前任和后继项目的平均等级），但这似乎不是一个可靠的解决方案，因为当插入许多新项目时它会很快遇到准确性问题。
我们还考虑将其实现为双向链表，每个项目都包含其前身和后继项目的 UUID。但是，这仍然需要在插入 1 个新项目时同步 3 个项目（或在删除 1 个项目时同步剩余的 2 个项目）。
优选地，我们希望使用只需要同步新插入的项目的数据结构或算法。这样的数据结构存在吗？
编辑：我们也需要能够处理将现有项目移动到不同位置的问题！
插值排名方法确实没有问题。只需根据表示 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)和并111获得1.001，然后转移到获得1001。这可以很好地用作插值。但请注意，最终1不必要地使它比任何一个操作数都长。一个简单的优化是将最后1一位与尾随零一起删除以获得简单1的 . 果然，1大约是我们希望的一半。
当然，如果您在同一位置进行多次插入（例如考虑在列表开头的连续插入），位向量会变长。这与在二叉树的同一点插入完全相同的现象。它长得又长又细。要解决此问题，您必须在同步期间通过使用最短的位向量重新编号来“重新平衡”，例如，对于 14，您将使用上面的序列。
添加
虽然我还没有尝试过，但 Postgres位字符串类型似乎足以满足我所描述的键。我需要验证的是整理顺序是否正确。
此外，同样的推理适用于任何k>=2. 第一项得到 key k/2。还有一个简单的优化可以防止在末尾和前面分别附加和前置元素的非常常见的情况导致长度为 O(n) 的键。对于这些情况，它保持 O(log n) （尽管在内部插入同一位置仍然可以在 p 次插入后产生 O(p) 键）。我会让你解决这个问题。使用 k=256，您可以使用不定长度的字节字符串。在 SQL 中，我相信你会想要varbinary(max). SQL 提供正确的字典排序顺序。如果你有一个插值操作的实现很容易BigInteger包类似于 Java 的。如果您喜欢人类可读的数据，您可以将字节字符串转换为例如十六进制字符串 (0-9a-f) 并存储它们。那么正常的 UTF8 字符串排序顺序是正确的。
您可以为每个项目添加两个字段 - “创建时间戳”和“插入之后”（包含插入新项目的项目的 ID）。同步列表后，发送所有新项目。该信息足以让您能够在另一侧构建列表。
收到新添加的项目列表后，执行以下操作（在接收端）：按创建时间戳排序，然后逐个进行，并使用“插入后”字段将新项目添加到适当的位置。
如果添加项目 A，然后在 A 之后添加 B，然后删除 A，您可能会遇到麻烦。如果发生这种情况，您还需要同步 A（基本上同步自上次同步以来在列表上发生的操作，而不仅仅是当前列表的内容）。它基本上是一种日志运输形式。
我认为，从广义上讲，运营转型可能与您在此处描述的问题有关。例如，考虑实时协作文本编辑的问题。
我们基本上有一个排序的项目（单词）列表，需要保持同步，并且可以在列表中随机添加/修改/删除。我看到的唯一主要区别是修改列表的周期性。（你说它不经常发生）
运营转型确实是一个很好的研究领域。我可以找到这篇博客文章提供指导和介绍。此外，对于 Google Wave 遇到的所有问题，他们实际上在 Operational Transform 领域取得了重大进展。看看这个。. 关于这个主题有相当多的文献。看看这个stackoverflow线程，以及关于差分同步
另一个让我印象深刻的相似之处是 Text Editors - Ropes中使用的数据结构。因此，如果您有操作日志，比如“索引 5 已删除”、“索引 6 已修改为 ABC”、“索引 8 已插入”，您现在可能需要做的是从系统 A 传输更改日志到系统 B，然后在另一侧按顺序重构操作。
另一个“务实的工程师”的选择是在系统 A 发生变化时简单地重建系统 B 上的整个列表。根据更改的实际频率和大小，这可能不像听起来那么糟糕。
我认为您可以在这里尝试一种交易方法。例如，您不会实际删除项目，而是将它们标记为删除，并且仅在同步期间提交更改。我不确定您应该选择哪种数据类型，这取决于您希望哪些操作更有效率（插入、删除、搜索或迭代）。
让我们在两个系统上都有以下初始状态：
|1| |2|
--- ---
|A| |A|
|B| |B|
|C| |C|
|D| |D|
之后，第一个系统将元素标记A为删除，第二个系统在和BC之间插入元素：BC
|1 | |2 |
------------ --------------
|A | |A |
|B[deleted]| |B |
|C | |BC[inserted]|
|D | |C |
|D |
两个系统都在考虑本地更改的情况下继续处理，系统 1 忽略元素B，系统 2 将元素BC视为正常元素。
当同步发生时：
据我了解，每个系统都会从其他系统接收列表快照，并且两个系统都会冻结处理，直到同步完成。
因此，每个系统依次迭代接收到的快照和本地列表，并将更改写入本地列表（根据修改后的时间戳解决可能的冲突），在“事务提交”之后，最终应用所有本地更改并删除有关它们的信息。例如系统一：
|1 pre-sync| |2-SNAPSHOT | |1 result|
------------ -------------- ----------
|A | <the same> |A | |A |
|B[deleted]| <delete B> |B |
<insert BC> |BC[inserted]| |BC |
|C | <same> |C | |C |
|D | <same> |D | |D |
系统唤醒并继续处理。
项目按插入顺序排序，移动可以实现同时删除和插入。此外，我认为可以不传输整个列表快照，而仅传输实际修改的项目列表。
我认为这里合适的数据结构是order statistic tree。为了统计树，您还需要维护子树的大小以及其他数据，大小字段有助于根据需要轻松按等级查找元素。排名、删除、更改位置、插入等所有操作都是O(logn).
你可以看看“镜头”，这是双向编程的概念。例如，您的问题似乎已经解决了我在本文中描述的“匹配镜头” 。
PrecedingItemID我已经通过在每个项目上包含一个（如果项目是有序列表的顶部/根），然后有一种本地缓存来保持所有项目的列表按排序顺序暂时解决了一个类似的问题（这纯粹是为了提高效率——因此您不必递归查询或构建基于PrecedingItemIDs 每次在本地客户端上重新排序时）。然后，当需要同步时，我会执行稍微昂贵的操作，即查找两个项目请求相同 PrecedingItemID 的情况。在这些情况下，我只是按创建时间排序（或者您想调和哪个获胜并先出现），将第二个（或其他）放在它后面，然后继续对列表进行排序。然后我将这个新的排序存储在本地排序缓存中，并继续使用它直到下一次同步（只要确保随时保持PrecedingItemID更新）。
我还没有对这种方法进行单元测试——所以我不能 100% 确定我没有错过一些有问题的冲突场景——但它至少在概念上似乎可以满足我的需求，这听起来与 OP 的需求相似。