We start by summarizing the recently proposed implementation of the first non-blocking concurrent interpolation search tree (C-IST) data structure. We then analyze the individual operations of the C-IST, and show that they are correct and linearizable. We furthermore show that lookup (and several other non-destructive operations) are wait-free, and that the insert and delete operations are lock-free. We continue by showing that the C-IST has the following properties. For arbitrary key distributions, this data structure ensures worst-case $O(\log n + p)$ amortized time for search, insertion and deletion traversals. When the input key distributions are smooth, lookups run in expected $O(\log \log n + p)$ time, and insertion and deletion run in expected amortized $O(\log \log n + p)$ time, where $p$ is a bound on the number of threads. Finally, we present an extended experimental evaluation of the non-blocking IST performance.
翻译:我们首先总结最近提出的第一个无阻并存的内插搜索树(C-IST)数据结构(C-IST)实施情况。我们然后分析C-IST的单个操作,并显示它们正确且可线性化。我们进一步显示,查找(和其他若干非破坏性操作)是无等待的,插入和删除操作是无锁的。我们继续显示,C-IST具有以下属性。对于任意的密钥分布,这个数据结构确保了最坏的情况$O(log n + p) 的摊销时间用于搜索、插入和删除跨行。当输入关键分布平稳时,在预期的$O(log\log n + p) 时间中进行查找,在预期的 美元(log\log n + p) 时间中插入和删除操作是无锁的。我们继续显示,对于任意的密钥分布,这个数据结构确保了最坏的 $O( n + p) amortized time 用于搜索、插入和删除。最后,我们对非阻截断 IST 性表现进行扩展的实验性评估。