database - 复制稳定 sortKey 的概念

Question

我正在寻找涵盖这个想法的 Material :

给定一个类似列表的数据结构(例如数据库表)，应该引入一个 sortKey 属性(列)

1. 反射(reflect)所需的排序顺序(ORDER BY sortKey)
2. 在列表中是唯一的
3. 可以在(排序的)列表中的任何位置插入
4. 是不可变的

要求 1-3 可以通过整数 sortKey 来实现，其中每次插入时，所有元素都可能被分配一个新的 sortKey。

要求 1-4 可以通过 tree'ish sortKey 来实现，例如十进制类型范围 (0.0, 1.0)；每个插入都会读取其前身和后继的 sortKey 并使用 sortKey(newItem) = ( sortKey(left) + sortKey(right) )/2

这个问题/解决方案是否有一个通用术语，我可以查找或者有人可以指点我文学。

谢谢!

Answer 1

并没有真正满足所有这些要求的好解决方案。 (3) + (4) 要求 key 长度可变，攻击者总能找到使 key 长度与插入的 key 数量成正比的插入序列。

这个问题被称为“在线列表标签问题”或“订单维护问题”，用 google 搜索这些术语会发现各种折衷方案，这些折衷方案可能对您有用，也可能没有用。

https://en.wikipedia.org/wiki/Order-maintenance_problem