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