摘要
针对异步共享内存模型下的并发搜索二叉树(BST)数据结构,提出了一种新的无锁实现方法。通过一种有效的节点重用策略,使得删除操作是无等待的,插入操作是无锁的。实验数据表明,该数据结构是高度可扩展的而且在高负载下能提供很高的吞吐量。
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.
出处
《计算机应用》
CSCD
北大核心
2012年第10期2736-2741,共6页
journal of Computer Applications
关键词
无锁搜索二叉树
无锁
无等待
可扩展
高吞吐量
unlocking binary search tree
lock-free
wait-free
scalable
high parallel
