Lock-Free Augmented Trees

本文介绍了一种常用的技术，即通过添加额外信息来增强现有的顺序数据结构，以支持更多的功能。例如，搜索树可以增强构建序统计树、区间树、tango树、链/剪枝树等顺序数据结构。 我们研究了如何设计并发的增强树型数据结构。我们提出了一种新的通用技术，可以增强无锁树来添加任何新的字段到每个树节点，只要新字段的值可以从节点及其子节点中的信息计算得出。这使得设计无锁、线性化的各种经典增强数据结构成为可能。作为第一个例子，我们给出了一个等待自由的trie，它存储了从$\{1,\ldots,N\}$中选择的元素集合$S$，并支持线性化的序统计查询，例如查找$S$的第$k$小元素。更新和查询需要$O(\log N)$步。我们还将我们的技术应用于无锁二叉搜索树(BST)，其中对树结构的更改使线性化论证更具挑战性。我们的增强BST支持在高度为$h$的树上以$O(h)$步的顺序统计查询。增强不影响更新的渐进运行时间。 对于我们的trie和BST，我们还给出了一种替代增强，以改进搜索和顺序统计查询，使其在$O(\log|S|)$步内运行（更新步骤的复杂性略有增加）。作为额外的奖励，我们的技术支持任意多点查询（如范围查询），其时间复杂度与相应的顺序数据结构相同。

论文旨在设计并实现并发的增强树数据结构，以支持各种查询操作，包括顺序统计查询和范围查询等。同时，论文还试图解决在并发环境下，锁定树数据结构的性能问题。

论文提出了一种新的通用技术，可以通过对每个树节点进行扩展，添加任何新字段，从而实现增强树的并发设计。这种技术可以应用于各种经典的增强数据结构，例如顺序统计树和区间树等。

论文提供了两个案例，分别是等待自由trie和二叉搜索树。这些增强树数据结构支持顺序统计查询和范围查询等操作，并且具有线性化特性。此外，论文还提供了一种替代方案，可以在更新操作的步骤复杂度略微增加的情况下，将查询操作的时间复杂度降至O(log |S|)。论文还支持任意多点查询，并且不会影响更新操作的渐近运行时间。

最近在这个领域中，还有一些相关研究，例如“Concurrent Binary Search Tree”和“Scalable Lock-Free Concurrent Binary Search Trees”。