解决方案

选择合适的容器是一件难事！

在默认情况下，SortAO 采用 Sorted-Block-Array 作为底层容器，但这也许并不是最优选择。

SortAO 目前提供了两类容器：

Block 系列

Block 系列的容器适用于中型数据（不超过 1,000,000 元素）。

可用于包装器的有序容器，包括：

更底层地，它们对应的无序容器包括：

Block 系列容器服务于中型数据，算法的性能偏向于查询，能为 不平衡的性能模式 提供可能。

对于突变操作（插入与删除），这些容器的复杂度均为 O(B + N/B)，但常数因子有所不同。
对于查询操作，这些容器的算法可以通过增大插入的常数因子，以此降低查询的复杂度量级。

Sorted-Block-Array 是最通用的结构，它平衡了访问与插入的性能。
在 500,000 元素的数据量下，其查询效率为原生数组的 1/2。
Sorted-Block-List 能在严格 O(1) 的时间内查询排名为 K 的元素，效率总是原生数组一致。
由于维护了更严格的物理块大小，其突变操作的效率低于前者。
Sorted-Block-Deque 大幅度提高了在极值处附近（较大范围）的突变操作效率。
在 500,000 元素的数据量下，其查询效率为原生数组的 3/4。

与常见的树形结构不同，它们的底层采用了更加连续的内存结构，因此对于中型数据，可以更好地利用 CPU 缓存，并更可能受到 JIT 的优化，性能往往更好（尤其是查询效率）。

Block 容器类似 C++ STL 的 vector，在插入/删除元素时，会导致游标失效的情况出现，且范围较大。

您可以阅读 Cursor 来了解有关游标的更多信息。

由于 Block 容器的游标失效场景有些细微的不同，详情可以参阅游标失效页面。

在 V8 中，高级数据结构的算法理论常数，通常会被内存延迟、分支预测失败和 GC 开销无情碾平。

我们测试了多种树形数据结构，包括严格的红黑树，均摊的 Splay，期望的 Zip Tree（一种在 2018 年提出的无旋 treap 的变体，具有代码简短的特点，且修改的效率为期望 O(1) ）。

但随机数据下，它们的效率几乎没有差别，这恐怕是由于 Cache Miss、写入屏障等多种因素导致的。

因此，我们目前只使用了 Splay 树作为树形结构的实现。

SplayTree 每次操作会将访问的节点提升到树的根节点，从而加速后续访问。对于具有热点数据的情况，其效率可以远高于任何数据结构。

如果你的业务场景中，数据的访问模式较为特殊，不妨测试一下这种数据结构的表现！

SplayTree 是一个树形结构，因此除非被删除，其游标不会物理失效（总是指向一个有效节点）。

但在插入、删除元素后，游标可能发生逻辑失效（其排名 index 发生了变化，而游标无法主动感知）。

此时可以采用 refresh() 方法进行刷新排名，详情可以参阅游标失效页面。