生成自定义排序顺序的键
ORDER BY 用户所说
引言
简介：要在关系数据库中表示用户定义的排序顺序，我们需要为“排序顺序”列生成可用于 ORDER BY 的值。我们如何生成这些值？
关系数据库提供按给定列或表达式排序数据的可能性，例如 SQL 中的 ORDER BY Name。它们通常不支持存储用户定义的排序顺序。为了表示这种排序顺序，我们通常会引入一个整数列。但是，整数字段可能需要频繁地重新编号，即不得不重新分配所有（或许多）列，即使只有一两个项目更改了位置或被插入。
本文展示了一种替代方法，通过生成字符串来换取（合理的）存储空间，以避免重新编号的需要，或至少将其大大推迟。
注意：我对这个解决方案不太满意。最终代码仍有些实验性。它提供了我需要的东西，但我无法摆脱我遗漏了一个明显简化的感觉。我将通过头脑风暴找到该解决方案的过程来弥补这一点，这对某些人来说可能很有趣。
传统解决方案
一个简单的解决方案是为排序键列使用整数，并按我们想要的顺序分配递增值。但这会带来一个小问题
hamlet 应该获得什么排序键？
通常，您会带有间隙分配数字，例如，猴子是 10，打字机是 20，那么 hamlet 可以得到 15。但是，在有限（通常非常少）次的插入后，我们会回到上述问题：N 和 N+1 之间没有整数。
解决该问题通常是“重新编号”项目：为所有项目或至少多个项目分配新的排序键。
我们能否生成仅影响插入项的排序键？
构建不同的解决方案
核心思想：查看上面的图像，它建议使用实数值而不是整数，并将 1.5（1 和 2 的平均值）作为排序键分配给hamlet。
初步分析：使用 IEEE 754 浮点值，因为它们被大多数系统支持，虽然存在一些问题，但主要问题是精度有限。一个 double，有 53 位，在仅仅 54 次糟糕的插入后可能会丢失精度。更糟糕的是，这会静默发生，因此需要显式检测。
一个小问题是如何在列表的开头或结尾添加项目。使用（最小值 - 1）或（最大值 + 1）分别很简单，但这很容易使精度问题变得更糟。
如果我有一把锤子：如果我们有一个无限精度的“大数”类型可用，所有这些问题原则上都会得到解决。但是，我们通常没有，即使有，通过要求更多存储也可以解决精度问题。
一个可能的解决方案是实现任意精度的数字，只进行递增、递减、两个数的平均值和比较操作。这看起来很简单，但是找到一种表示方式，使得比较操作是简单的字符串比较（或类似常用方式）让我最困扰。
此时，我感到非常卡壳，并纠结了各种细微的变化。好消息是解决方案并不紧急，我可以把它放在脑后几天。
顿悟：既然我在表示法上卡住了，我暂时忽略了这个问题，专注于更简单的平均值计算，并已经完善了一些细节：而不是由数字 '0' .. '9' 组成的字符串，我可以使用整个字母空间。我可以使用 ASCII 字符 '!' == 33 ... '~' == 126 作为基数 94 的数字。在计算平均值时，我不必特别精确，如果我的“近似平均值”介于两个指定的排序键之间，我可以截断尾随数字。这可以限制在同一位置发生插入时所需数字数量的可能过度的增长。对于算法的实验，我只是在实际列表之前和之后使用了一些“保护值”，所以所有操作都是在两个值之间插入。由于目前我不在乎“-1”和“+1”，我只关注小数点后的数字，这使得字符串易于比较。
我花了一段时间才注意到我已经解决了我的问题。
1. 将所有值保持在两个任意保护值之间，我唯一需要的操作就是平均两个值
2. 将所有值保持在 0 和 1 之间将允许对小数点后的位置进行简单的字符串表示，其中字符串比较几乎等同于数字比较（除了某些不影响我们目的的边缘情况外，有一些例外）。
突然击中我的不是解决方案本身，而是意识到我手中已经有了解决方案（并且我已经舒适地承认的程度远远超过了我舒适的程度，我已经用它做了我那些愚蠢的小测试）。这种感觉就像是灯泡超新星爆发，同时又非常谦卑。
调整：我仍然不得不对解决方案进行大量调整，比我预期的要多。我最终实现了一个“几乎递增”和“几乎递减”来处理常见操作的前缀/追加情况，但它们很糟糕，因为它们会迅速增加字符串长度。我仍然有两个我可能永远不会执行的分支（并且在我的测试中也从未执行过），但我不愿意删除它们，因为我无法证明它们不会被执行。我调整了不同的情况和一些常数（例如，字符串扩展多少“数字”）以避免字符串过度增长。我尝试构建各种病态案例，以使这个相当启发式导出的算法更加健壮。
解决方案
排序键是表示有理数小数点后数字的字符串，其字符串比较与数字比较非常相似，并且可以在遵守某些约束的情况下使用。
从十进制系统进行琐碎的映射将使用 '0' .. '9' 作为字符。这里的示例使用 'a' .. 'z'，因为这更具说明性。实际实现可以使用任何连续的字符范围（只要多于 3 个元素）。
字符串不能以 'a' 结尾，因为没有字符串可以放在 "x" 和 "xa" 之间。
为这些值实现了三个操作
CStringA Before(CStringA const & v)
返回一个比 v 小的值。
在大多数情况下，这是一个简单的递减
Before("abc") == "abb"<br>
Before("abb") == "aaz" (do not end in 'a' rule)<br>
Before("ab") == "aaz" (since this cannot be decremented further, expand. Think of 0.009 < 0.01)
实际上，我们追加多个 'z'，以防止在总是插入到第一个元素之前时字符串过度增长
如果只追加一个 'z'，我们在必须追加一次之前只能“递减” 25 次。通过追加“zz”，我们可以在必须扩展之前递减 26*25 次，通过追加“zzz”，我们可以递减 26*26*25 次。
CStringA After(CStringA const & v)
返回一个比 v 大的值。
在大多数情况下，这是一个简单的递增
Before("abc") == "abd"<br>
Before("abz") == "acb" (again, do not end in 'a'
rule)<br>
Before("zzz") == "zzzab" (cannot incremented further, expand. Think of 0.99901 > 0.999)
同样，实际上，我们追加多个字符，并且我们必须遵守不要以 'a' 结尾的规则，所以我们追加 "ab"。
CStringA Between(CStringA const & a, CString const & b)
返回一个比 a 大且比 b 小的值。
实现有点复杂，详情请参阅实现。
测试
除了对特定值的一些单元测试（或类似的测试）之外，我还运行了各种操作来检查过度增长、某些参数的影响以及各种可能的病态案例。
测试总是包含 5 个顺序起始值“m” .. “q”，以及（最多）100000 个以下操作
- 在所有值之前插入
- 在所有值之后插入
- 在随机位置的两个值之间插入
- 删除一个随机值
- 在固定位置插入（在索引 6 和 7 之间）
测试给出了这些操作的百分比。请注意，由于显示舍入，百分比并不总是加起来为 100。
基线测试
基线测试使用了各种操作的“健康混合”，并最终导致排序键的最大长度为 22。对于一个包含 100005 个值的向量和一个狂野的猴子用户来说，这不算差。
| 字符集在前面插入 插入之间 在后面插入 删除 插入 @ 索引 7 扩展 最大长度 |
'a' - 'z' 18% 37% 36% 9% 0% 3 22 |
"Expand By" 表示当长度（即精度）需要增加时追加到字符串的字符数。
仅插入
| 字符集 在前面插入 插入之间 在后面插入 删除 插入 @ 索引 7 扩展长度 最大长度 |
'a' - 'z' 18% 37% 36% 9% 0% 3 22 |
'a' - 'z' 0% 100% 0% 0% 0% 3 43 |
左边是“健康的混合”基线测试，右边是仅包含插入的测试。我们不像顺序插入那样擅长随机插入，但仍然不错。
扩展字符集
| 字符集 在前面插入 插入之间 在后面插入 删除 插入 @ 索引 7 扩展长度 最大长度 |
'a' - 'z' 18% 37% 36% 9% 0% 3 22 |
'!' - '~' 18% 37% 36% 9% 0% 3 22 |
'a' - 'z' 18% 37% 36% 9% 0% 4 29 |
'a' - 'z' 18% 37% 36% 9% 0% 2 113 |
'!' - '~' 18% 37% 36% 9% 0% 2 15 |
令人惊讶的是，将字符集从 26 个扩展到 94 个字符在最大长度上没有区别。但是，正如最后一列所示，增加字符集可以减少扩展长度。
将“扩展长度”增加到 4 并不会显著增加生成键的长度（从 22 增加到 29）。
使用较小的字符集 'a'-'z'，减小“扩展长度”实际上也减小了排序键的最大长度，达到 113。仍然可以接受，已经表明了之前观察到的激进增长。
使用扩展字符集，减小“扩展长度”实际上也减小了最大排序键长度。
这表明具有短“扩展长度”的顺序插入可能变得关键，而稍长的“扩展长度”则更稳定（尽管对于随机插入而言略差）。
最佳“扩展长度”取决于字符范围、预期的项目总数以及插入模式。但是，3 在广泛的输入中似乎能产生可接受的结果。
一个自适应当前排序键长度的“扩展长度”可能更具自适应性，但似乎不是必需的。
进一步的测试结果可在源码中找到，但它们不太有趣。
批判性审查
不清楚此努力是否对相关应用程序真正必要。很少有用户希望手动为 100K 个项目分配排序顺序，并且对于自动生成的数据，通常有时间戳或类似的排序标准可用。
对于用户可能希望提供特定顺序的典型用例，20-30 个项目可能已经很多了，并且带有项目之间足够空间的基于整数的方案可能就足够了。尽管频繁插入和移动，重新编号项目可能偶尔会变得必要，但不太可能导致性能问题。
如果影响的项目非常多，或者修改多个行不仅是性能问题，还可能是并发、锁定或 API 问题，那么该算法可能会有重要的应用。
历史
2012 年 9 月 5 日：发布