项目标有修改时间戳以检测编辑.项目由UUID标识,以避免在插入新项目时发生冲突(与使用自动递增整数相反).检测到同步新UUID并将其复制到另一个系统时.删除也是如此.
上述数据结构适用于无序列表,但我们如何处理排序？如果我们添加了一个整数“rank”,那么在插入新项目时需要重新编号(因此需要同步所有后续项目,因为只有1次插入).或者,我们可以使用小数排名(使用前任和后续项目的平均排名),但这似乎不是一个强大的解决方案,因为当插入许多新项目时,它会很快遇到准确性问题.
我们还考虑将其作为双重链接列表实现,每个项目都包含其前任和后续项目的UUID.但是,当插入1个新项目时,仍然需要同步3个项目(或者当删除1个项目时同步2个剩余项目).
优选地,我们想要使用仅需要同步新插入的项目的数据结构或算法.这样的数据结构是否存在？
编辑：我们需要能够处理将现有项目移动到其他位置！
解决方法
该系统唯一的不便之处在于空位向量给出的最小可能密钥为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大约是我们希望的一半.
当然,如果在同一位置进行多次插入(例如,在列表的开头插入连续插入),位向量将变长.这与插入二叉树中相同点的现象完全相同.它长得又长又细.要解决此问题,您必须在同步期间通过使用最短的可能位向量重新编号来“重新平衡”,例如：对于14,您将使用上面的序列.
加成
虽然我没有尝试过,但Postgres bit string type似乎足以满足我所描述的按键.我需要验证的是整理顺序是正确的.
此外,对于任何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字符串排序顺序是正确的.
