在高效的并发有序索引研究中，传统的二叉搜索树、B树、跳表等结构主要关注于提供良好的最坏情况保证。然而，实际工作负载中，对象的访问速率往往不均匀，导致访问分布的不均衡。
尽管存在多种高效的分布自适应数据结构，但在并发情况下实现这些结构的效率通常较为复杂。
自调整树（Splay Tree）是最突出的分布自适应数据结构，其主要优点是不会存储任何平衡信息，并且在极度偏斜的工作负载下（如Zipfian工作负载）提供合理的性能提升。
本文提出了一种类似于自调整树的旋转设计，应用于并发二叉搜索树。不同于将访问节点移动到根节点，这一旋转设计采用基于节点访问次数计算的静态最优复杂度的两个深度阈值：只有当节点深度显著超过上阈值时，才会进行旋转，而旋转将在达到下阈值之前停止。
此设计旨在保留自调整树在偏斜工作负载下的主要实际优势，同时减少根节点附近的竞争。
我们提出了两种旋转设计变体：一种为每个节点使用精确的64位访问计数器，另一种使用6位近似计数器。我们证明了对应于顺序只读树的静态最优性，并通过在Bronson等人的并发AVL树上实现这两种旋转设计进行了评估。
实验表明，该方法能够在多种偏斜工作负载下提升吞吐量。
博主点评： 该研究在并发数据结构领域提出了创新的解决方案，通过利用自调整树的优势，有效提升了在不均匀负载下的性能，展示了理论与实践的结合，值得关注与深入研究。