Before Reading

相信在看过前几个专题以后，读者一定会发现笔者对英语双关钟爱有加（

本期题目最早设想了另一个更抖机灵的名字：Why does double trouble?

因为太冷了把本人冻感冒了遂改名（改后也超冷的好吧

这些分析对于Existimer的开发作用不大。但是Existimer本身作为一个学习性的项目，偶尔摘一下路边的野花也没什么不应该的。

本篇是Existimer开发设计的第4篇。本篇不同于前面几篇，主要是从数学、算法和实验的视角撰写，因为数学不过关而被迫做实验）也是笔者自去年冬天以来第一次深入讨论算法。本篇不会直接使用AI生成内容，因此语言可能更加生涩一点。

建议跳过概述和引言，考研复习累了闲暇里水的无营养文字就不要看了（捂脸

Abstract

在任务列表、看板、协作文档等多种应用中，维护对象的顺序并支持在任意位置插入或移动元素，是常见且基础的需求。通常做法是为每个元素分配一个"顺序索引"（order index），插入或移动时仅调整相关索引，最终通过索引排序还原正确排列。

在这一设计中，索引排序算法的选择直接影响系统的整体可用性和性能表现。优秀的排序算法能够在高密度插入场景下保持低重排频率，确保索引系统长期稳定可用，同时将资源消耗控制在合理范围。

本文从对比 int64 整数索引 与 fp64 浮点索引 出发，探讨多种索引排序算法的适用场景，纠正部分常见误解。特别指出，整数索引并非天生劣势。在适当设计下，整数索引的性能和可用性可以接近甚至超越浮点索引。此外，结合类似 LexoRank 的字符索引方法，我们提出基于路径编码的排序方案，使用64位空间实现最坏情况下 64 次插入操作；或利用 BLOB 存储方式，获得比字符串编码或 LexoRank 更优的性能表现。

一个简单的后续实验结果展示

一个简单的后续实验结果展示

Introduction

顺序维护索引算法大致分为三类：

  1. 数值索引（Numeric Indexing）
    以整数或浮点数为基础，利用其天然大小关系完成排序。该类算法实现简洁，存储紧凑，适合轻量场景。但在高频插入下，若不能有效保持值的稀疏度，容易出现值碰撞和频繁重排，带来性能瓶颈。
  2. 字典索引（Lexicographic Indexing）
    通过字符串编码（如 base62、分级编码等）模拟无限精度的数值，理论上支持无限次插入而无需重排。字典索引的通用性极强，且天然支持分布式场景。但字符串长度增长需要控制，否则影响存储与查询性能，通常需配合辅助策略限制增长。
  3. 结构性索引（Structure-based Indexing）
    如链表、跳表等数据结构，依靠指针维护顺序，天然支持高频插入移动且不存在精度限制。但其随机访问性能差，且难以与数据库等线性存储系统高效整合，因而在多数场景不被采用。

在数值索引中，整数（int64）和浮点（fp64）是最主流的两种实现方式。现实中，fp64索引因其能通过中间值计算支持较多插入而广泛使用，int64索引则较少被采纳。一个普遍观点是"int64不如fp64"，这其实是基于对两者特性的误解。

实际上，int64索引的瓶颈常被认为是缺乏足够的中间可插入值，但这种观点却忽视了int64极限精度大于fp64这一关键事实。利用大于2^52的初始间隔，int64索引在小规模数据及适当插入密度下，表现出的插入容量和稳定性可远远超过fp64，且因整数操作精度无误差，整体更具确定性和效率。

基于对 LexoRank 等字典索引的研究，结合传统int64索引，我们提出了一种更加紧凑的索引方法。将路径信息存入单个int64字段，理论上支持最坏情况下达 64 次插入操作。若采用 BLOB 形式存储编码，则可获得相较于字符编码或LexoRank更优的性能和空间表现。

【PART I】Unfair Competition

首先简单解释一下int64索引和fp64索引的原理，这有助于我们梳理整个问题。

We Need An Unbridgeable Gap

Order Leads To Chaos

整型天然表明了顺序。如果我们可以一次性录入所有记录，并永不重排，一个自增的整型order index便足以处理这种情况。好啦，我们的工作结束了，是时候奖励一下自己了，去泡杯咖啡吧(表达了作者对咖啡的喜爱之情（ 咖啡还会在后文中出现)。然而现实没有那么理想，阻碍我们休息的罪魁祸首主要有两点：

  • 记录不会一次性全部录入，而是会随着使用增长或减少，在某些场景下可能极端多或极端少
  • 记录一般会在录入后调整顺序，在极端情况下（比如UI过于华丽，用户乐于反复操作以欣赏你的动效，或者是仅仅出于无聊会像跳棋一样（左脚踩右脚登天）逐渐耗尽排序能力

对于第一点处理可以很简单（尽管埋下了隐患），只是使用整型作为order index无需过多担心，增加就在最大值上加1为新的索引，减少删除掉就好。对于第二点，我们也不必像给小孩子讲计算机或者数学一样，打排队的比方。总之很好理解，如果Order Index的自增间隔为1，即不预留空间，除非后续排序或删除，否则对于索引总数为$N$的序列，插入或排序的位于$M$的记录的代价将是$O(N-M)$，自$M$起后面位置的必须全部重排。当$N\gg M$时，不考虑查询的时间复杂度为$O(N)$。在可用的情况下，不考虑查询的插入时间复杂度为$O(1)$，利用数据库索引查找的时间复杂度为$O(\log N)$，否则为$O(N)$。因此如果不预留时间，则会频繁触发全体重排，最糟情况下，考虑B-tree查询的$n$次插入或排序时间复杂度为

$$ O\!\left(\sum_{k=1}^{n} \left(\underbrace{\log(N+k)}_{\text{查找}}+\underbrace{(N+k)}_{\text{重排}}\right)\right) = O\!\left(nN + \tfrac{n(n+1)}{2} + \sum_{k=1}^n\log(N+k)\right) = O\!\left(nN + \tfrac{n(n+1)}{2} + n\log(N+n)\right) \tag*{(1)} $$

当$\frac{n}{N} = a,\ a \in \mathbb{R},\ a \neq 0$时，式(1)可以化简

$$ O\!\left(nN + \tfrac{n(n+1)}{2} + n\log(N+n)\right) = O(nN + n^2) \tag*{(2)} $$

设数据库单位查读写时间分别为$t_s$、$t_r$和$t_w$，某自$k \ll N$位向后重排则有

$$ T = t_w + t_s \log N + t_r + (t_s \log N + t_w)N \tag*{(3)} $$

若全部重排则为

$$ T_\text{all} = T_s + T_\text{update} = (t_s \log N + t_w)N \tag*{(4)} $$

Well done, but actually (3)式和(4)式相当的不负责任。在我配备Ryzen9 7950X和Samsung 990EVO Plus的设备上，理论模型和实际重排时间始终差100倍左右，如下图所示

实际重排时间与理论时间对比

实际重排时间与理论时间对比

其中$t_w\approx1.07\times10^{-7}$s，$t_s\approx9.83\times10^{-6}$s，$t_r\approx9.83\times10^{-6}$s。你可能注意到，这组参数格外的滑稽荒唐，因为写时间竟然短于另外两个。这是因为写操作开启了事务(TRANSACTION)，而查和读则一般不这样做。笔者实在是没有时间精力刨根问底，因此100这个Magic Number让人产生了小小的遗憾，期待有人为我解惑。我的猜测是这样的：

  • 在实际使用中，SQLite会自动优化
  • 单操作测量有误
  • 建模使用的时间参数不对
  • 建模有误（可是整整100倍是从何而来，令人费解

如果时间复杂度计算本身是正确的，便可以参考下面的图像（或者大家早就烂熟于心），看起来很吓人，但不算非常糟糕。对于轻量的使用场景比如ToDo-List类应用，在总任务数小于$10^6$时都是可等的，延迟在几百毫秒左右。考虑到接口等消耗，$10^4$时也是绰绰有余。

常见时间复杂度可视对比

常见时间复杂度可视对比

可是如果有用户是任务狂人呢？我们当然也可以选择推开键盘，建议用户和我们一样，在适当的时候来杯咖啡，而不是过于执着。 那么本文就此结束，又到了愉快的咖啡时间（

还不到时候。如此频繁的触发重排，将长期占用磁盘读写和CPU资源，而且非常不利于并发。既然做了这么多工作，为什么不多做一点呢？

Sooner Or Later

很自然的会想到在一个Order Index前后留出空间，方便未来的位置调整。我们引入间隙缓冲(Gap Buffer)来实现这一目的。最简单的实现就是把自增间隙调大。有了间隙之后，插入就可以采用不同的策略：二分或者随机。随机策略除了引入混乱以外，似乎没有明显的优势；而针对二分策略，间隙则以2的幂为佳，这样才能充分利用空间。如果用户的排序行为是随机的，这个问题又简化成一种二项分布。虽然笔者在几门数学课程中，得分最高的就是概率论，奈何数二不考，高中知识也忘干净了，就不再展开了。总之最好的情况就是填满间隙，最差的情况就是只向一边插入或移动，导致局部过密，间隙失效。最差情况下的操作次数遵循下面公式：

$$ n = \left\lfloor \log_2 N_\text{Gap} \right\rfloor \tag*{(5)} $$

将Gap Buffer设成1024时的插入极限

将Gap Buffer设成1024时的插入极限

看起来也太不划算了。这意味着，Gap设置成1024只能获得10次绝对安心插入，再多就要开始豪赌了。这样看来，退化到$\text{Gap}=1$的情况只是时间问题，间隙缓冲没法从根本上解决问题，甚至引入了新的问题：如果我们为了降低重排概率而将Gap设置的非常大比如$2^{63}$，这样自增的数量就有限了（在$Gap=2^{63}$的情况下算上0只能容下两个索引），总索引数目就会很小了。不过在我们不需要很多索引的时候，间隙缓冲不失为一种方法，反正不需要写额外的逻辑，不用白不用。

A Finite Infinity

一个简单的review：

Mantissa(译作尾数，或Fraction)部分决定精度，指数位记录原始指数(e)决定范围

IEEE‑754 双精度采用 1023 作为指数偏移量（bias）

计算方法如下：

$$ \text{Value}=\left(-1\right)^\text{sign}\times\left(\text{1.fraction}\right)\times2^E,\; E=e-\text{bias}.\tag*{(5)} $$

fp64存储示意图

fp64存储示意图

浮点索引也是对半的算法，不过理论上能无限小。实际fp64在线性尺度上有

$$ \forall\,n\in\mathbb{Z};\;\forall\,s\in\bigl[\,2^n,2^{n+1}\,\bigr):\quad s^{+}-s=2^{\,n-52},\,s^+=\operatorname{nextafter}(s,\ +\infty).\tag*{(6)} $$

基于上式我们给出fp64最小精度定义：

$$ ulp(x)=2^{n-52}\ (n=\lfloor\log_2{|x|}\rfloor)\tag*{(7)} $$

这也就意味着fp64在任意$2^n$区间内至多二分52次就达到精度极限。用数学形式表达（博客中!=有几处渲染不出来，自行脑补即可）：

$$ \exist N_A,N_B\in\mathbb{R},N_A\neq N_B:\\ \mathrm{diff}=\frac{1}{2}|N_A - N_B| \lt ulp\left(\max\{|N_A|,|N_B|\}\right) \ \Longrightarrow\ \mathrm{fl}(\mathrm{diff})=0\neq itself.\\ let\ N_C=\min{\{N_A,N_B\}}+\mathrm{diff},\quad then\ \mathrm{fl}(N_C)\neq itself.\tag*{(8)} $$

这对比起int64并没有什么，int64不过最小精度固定为1而已，如果自增间隔设为$2^{52}$，也是至多二分52次。有别于int64 i+=n的线性自增，fp64应当采用i*=2指数自增。然而糟糕的是，精度的变化将不得不引入额外的设计。一般来说，意向排序区间跨域多个$2^n$区间是很正常的事情，但随着最小精度逐渐变大，数据将变得稀疏起来，还会拖累前面的稠密区间：你不得不按照最差的情况设计。

fp64数密度示意图

fp64数密度示意图

上面不是MD取色图，而是展示了fp64的数密度，我们取了ulp的倒数，以此表示单位间隔内能表示的数的总量。不需要更多图表来展示或放大什么的，事实上我们随便截取小段放大，都会像上图一样（是除了颜色外的完全一致！）：绝大部分可取的数都被包括在第一个像素里了。没有很好的可视化手段能表现出这种不均匀，能表现出来的都经过数据处理而不够震撼。如果绘制函数图像，我们将得到一个直角，近乎无限垂直的两条线。

这还不是最糟的。应当注意到有人试图效仿整数索引的Gap Buffer思想，采用固定的间隔。好啦，现在我们不仅有不均匀的精度，还引入了额外的舍入误差，这下真是Double Trouble了（此处需要笑点解析

在最好情况下，fp64不过和int64一样。而它所暴露的问题需要专门考虑，怎么用好它又是一门学问。

【Part II】Unfair Competition

经过上面的分析，fp64无论如何都打不赢int64了（悲

其实是分析在后的，实验在前，于是就贴上实验结果吧。不过也探讨了一些其他有意思的主题

Prompt Master

笔者没能力写这么多Python代码，完全依赖通义灵码和ChatGPT，自己主要进行的就是实验设计和指导了。如需分析实验代码请前往项目仓库自取，下面仅就实验设计和实验结果进行讨论。

我们没有直接进行实验，而是对实际应用场景进行了抽象建模。简而概之就是对Gap Buffer取对数再取整得到最大操作次数，利用这个最大值初始化场上元素，计算移动操作后在某个位置附近操作的剩余次数，如果为0则标记为失败（对应着插入后前后无空间必须重排的情况，这取决于重排策略。也可以选择忽略本次，直到真正无法插入时再重排，那样就多一次操作机会）。

虽然在上面的分析中，已经明确了fp64的“正确使用方法”，但是鉴于大部分都是采用的退化用法（即采用固定增间隔。这倒未必是件坏事，指数间隔的维护也要引入额外逻辑，而且数密度绝对不均匀），故也采用该用法。

在实验过程中的主要变量：

  • 元素最大总数
  • AUTO_INCREMENT 是否开启自增，即元素是一开始就全部准备好的，还是在实验过程中加入的（后者更符合实际情景）
  • INCREMENT_intERVAL 每移动几次添加一个新元素，直到设定的总数上限
  • int64组的Gap Buffer大小的对数
  • MIN_MOVES & MAX_MOVES 移动次数最小值、最大值
  • STEPS 移动次数增长步长
  • NUM_EXPERIMENTS每组移动的实验次数（如移动100次独立重复2000次，移动110次独立重复2000次）

基于上面设计了1组基础实验和5组对照实验：

  1. 基础实验：元素总数53，开启自增，自增间隔10，Gap Buffer对数取10（即1024），移动最小次数1，最大次数2000，移动次数增长步长10，实验重复次数2000
  2. 关闭自增：同实验1，关闭元素数量自增，一开始就全部就位
  3. 自增间隔5：同实验1，元素自增间隔为5次移动
  4. 自增间隔2：同实验1，元素自增间隔为2次移动
  5. 元素总数20：同实验1，元素总数为20个
  6. 元素总数256：同实验1，元素总数256个

Hello Matplotlib

我们认为$FR\leq5\%$时可以接受，并以此$FR_5$值为衡量可用性的标准。

实验1、2对照：

自增对失败率的影响

自增对失败率的影响

可见差距明显。无论是int64组还是fp64组，关闭自增均对可用性有非常大的好处。在元素少的时候，往往会快速消耗可操作次数。在元素数量少时重排代价小，操作次数不重要；而元素数量多时，重排代价高，操作次数更加宝贵。这样看来，早期不重排减少的计算资源反而可能为未来埋了雷。因此可以考虑在数据规模小时以合适的代价更积极的重排，避免代价升级。

实验1、3、4对照：

进一步印证了上面的讨论。这也许会对我们的缓存策略有一定的启示。对于需要索引的数据，我们尽量缓存在内存中（不是整条数据，仅仅保留唯一标识和索引本身），在内存中进行排序，择机一次性插入（尤其是数据量小的时候，必要时完全在内存中进行排序）。

实验1、5、6对照：

不同元素总数对失败率的影响

不同元素总数对失败率的影响

上图说明，在开启自增的情况下，索引失效的主要原因还是前期自增不够快。这个瓶颈无法通过增加元素总数来得到明显稀释（256元素时的$FR_5$值和53元素时相比没有明显差别）。但是在少操作次数的时候，又对元素总数敏感（20元素时的$FR_5$值比53元素小不少）。这对小数据量的轻量场景没有什么意义，因为20元素和53元素的重排成本都不大。元素多唯一的好处就是，在操作次数极多时，失败率比较低（但是没有用，大于50%时重排只是早晚的事情）。

因此主要的优化手段还是保证初始数据均匀度，否则最开始的几条索引将快速失效，从而引发重排。也可以考虑引入局部重排，来缓解这种局部过密的情况。

【Part III】 Beyond The Edge

我们可以看到，利用基于有限位的类型排序的能力会指数级的衰退。我们当然知道为什么会这样，但是这依然是一个值得深挖的问题。这里所谓值得深挖的主要是指，在算法的设计途中，我们有很多“理所当然”的想法，或顺应了思维习惯，或参考了通常的做法。让我们梳理一下之前我们的算法究竟做了一件什么事情。

目前文章里深入讨论过的算法的核心不过如此：

  1. 利用了实数在一定范围内天然的排序能力。整型、浮点等类型天然具有大小比较的能力，我们把排序能力建立在了这种自然秩序上；
  2. 利用了两实数之间的间隙内化了插入这一事实。这种做法看起来只是简单进行了运算，但实际呈现出来的结构是一种“扁平树”；
  3. 利用了二分或Gap Buffer等方法稀疏编码空间。这提升了极端情况下的算法表现。

对此我们提出3点疑问：

  1. 如果此类有序类型的大小有限，是否可以采用更大密度或更大容量的类型，抑或是二者兼得？
  2. 如果分辨颗粒度限制了插入的能力，是否可以局部细化粒度或动态调整粒度？
  3. 稀疏编码空间的大部分区段都有充分的排序能力，而失效主要是部分区段过于稠密导致的。是否可以稀释稠密区段？（当然不能通过全面重排的方法）

笔者不得不承认，这里有先射箭后画靶的嫌疑。但我们相信讨论的过程比结果更重要（如果您看到这里，相信也是对这个讨论更感兴趣。讨论的结果在一开始就给出了，稍加思索就可以理解是如何实现的），更何况我们距离问题的根本又更近一步了。因此也就不给出参考答案了。

在我们搞清楚这种设计逻辑或哲学以前，早就有人巧妙的解决了上面的问题了。不妨参考一下他们的方案。

让我们先从最常见的无限（理论上）索引算法“字典索引”开始，再讨论一下LexoRank和它的“桶”巧思，最后给出我们的办法。对其他算法只是简单的介绍，以说明它们解决了什么问题。

Char-mancy

不是Necromancy（

我们很早就用字符串来绕开一些限制了，这在C/C++算法题目中尤为常见。笔者还记得初中时发现这种“歪门邪道”（在没有时间复杂度要求的部分场景下堪称逃课神器）的震惊。最简单的应用就是作大数运算。这一切可行归根到底是String本质上还是整型序列，处理ASCII码的难度并不比普通整型大。基于字符串的字典索引算法的实现方法我们就不再介绍，很好理解。除此之外，利用字符串进行索引的还有分数索引。我们划分数索引和字典索引的依据并不是其存储方式。比如通常意义上的分数索引，在这里我们应该将其划分给数索引，本质上即通过字符串拓展的浮点索引。

我们举一个简单的例子：同样是123/2/13三个数，对于字典索引顺序应当是123<13<2，而对于数索引则是2<13<123。字典索引的排序是按位的，元素的顺序需要每个层级分别确定；而数索引的排序则是由数值整体决定。如果采用ASCII码作为字典，则每层消耗1字节。在频繁向一侧插入时，资源占用会迅速增长至其他方法的数倍。

以LexoRank为代表的字典索引为了避免或减小这些问题，采用了不同的策略：

  1. Return a new string that sorts between two given strings：S tack Overflow上的一个帖子，质量很高，详细讲解了如何确保只在必要时增加层数。这一设计旨在避免层数失控。然而这一设计面向的是完全随机的插入，在排序能力上面对优化后的数索引未必有优势。
  2. Managing LexoRank（这是算法创始团队的技术支持文档）和Лексоранги — что это такое и как их использовать для эффективной сортировки списков（如同大部分文章一样介绍了LexoRank，但是篇幅比较短因此列在这里）以及LexoRank とは何か？（在用日语解释了这一算法的实现后，本文澄清了对桶即Bucket这一概念的偏见）：这些文章介绍了LexoRank和它的桶策略。通常认为，桶是在字典耗尽时的解决方法。但文章指出，桶的关键作用在于保证重排时，对表查询时仍然保持原有顺序不变。所以桶本身并不是避免了重排，而是避免了重排时的顺序混乱。具体原理请参阅原文。

应当注意到，同一时间只能有一个活跃桶，Bucket应当作为一个独立字段，而非加在Rank字段前面。

The Other Path

  • 方案1：int64路径编码，问题：sqlite没有无符号整型
  • 方案2：8Byte BLOB路径编码，问题：性能不如int64
  • 方案3：BLOB路径编码，问题：Dart处理麻烦
  • 方案4：二进制编码TEXT压缩路径编码+自定义collection加速+解码，问题：可能得不偿失

基于之前的讨论，上面是我想到的一些方法。整体上来说，方案2和方案3比较可取。关于它们性能之间的讨论，因为要做更多的实验，而且结果比较显然，没有太大实际意义，所以不再深入了。

上述部分算法性能表现示意图

上述部分算法性能表现示意图

With Extra Pages

在这里花费的时间是最多的，我一直在想有什么进一步优化的办法，不过还真就没有多少好点子。关于具体算法实现请参考未来整理的更正式的版本以及项目源代码。