Efficient Lock-free B-trees
đź“ś Abstract
In this paper, an efficient implementation of a lock-free B-tree is described. The B-tree is a useful and well-known data structure, especially for databases and file systems. A few lock-free B-trees have been implemented, but they require instructions beyond those provided by most architectures, such as the double-word compare-and-swap (CAS) or they are complex and do not perform well. This paper presents a new algorithm that is both simple and efficient, making use of the single-word CAS provided by most architectures, and its performance has been measured to show that it is better than locking-based schemes in most cases.
✨ Summary
The paper “Efficient Lock-free B-trees” by J. D. Valois was published in 2004 and introduced a novel implementation of lock-free B-trees that leveraged the single-word compare-and-swap (CAS) operation, a feature available in most architectures. This was significant because previous implementations either required more complex operations, like the double-word CAS, or did not perform efficiently. Valois’s implementation emphasized simplicity and performance, aiming to outperform locking-based schemes, which can introduce delays due to contention for locks.
Despite the potential relevance of this work in concurrent computing, there are no widely recognized subsequent papers or industry applications that directly cite this specific work according to available databases and web searches. However, the topic itself continues to be relevant in fields that require efficient, concurrent data structure manipulation such as database systems, with ongoing research in more advanced non-blocking algorithms that build on the principles of lock-free programming introduced by studies like this one.