论文标题
非阻止插值搜索树的分析和评估
Analysis and Evaluation of Non-Blocking Interpolation Search Trees
论文作者
论文摘要
我们首先总结了最近提出的第一个非阻滞并发插值搜索树（C-ist）数据结构的实现。然后，我们分析C-ist的各个操作，并表明它们是正确且可线化的。我们此外表明，查找（以及其他几个非破坏性操作）是不含等待的，并且插入和删除操作是无锁的。我们继续证明C-ist具有以下属性。对于任意的密钥分布，此数据结构可确保最坏情况$ o（\ log n + p）$摊销时间用于搜索，插入和删除遍历。当输入密钥分布平滑时，查找以预期的$ o（\ log \ log n + p）$时间运行，并且插入和删除在预期的amortized $ o（\ log \ log \ log \ log n + p）$时间中，其中$ p $是线程数的限制。最后，我们提出了对非阻滞IST性能的扩展实验评估。
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.
