A new scheme for unlocking implementation of concurrent Binary Search Tree ( BST) based on asynchronous shared memory systems was provided in this paper. This scheme possessed two outstanding advantages: The deletion is wait-free, and the insertion is lock-free. The experimental results show that this scheme is highly scalable and can produce high throughputs under heavy load.%针对异步共享内存模型下的并发搜索二叉树(BST)数据结构,提出了一种新的无锁实现方法.通过一种有效的节点重用策略,使得删除操作是无等待的,插入操作是无锁的.实验数据表明,该数据结构是高度可扩展的而且在高负载下能提供很高的吞吐量.
展开▼