Lock-Free Binary Search Tree Based on Leaf Search

2. Lock-Free Binary Search Tree

CAS are one of the basic atomic instructions, which now are supported by almost all processors. One CAS instruction has three operands: memory address value V, the old expected value A, and the new value B. The value in V can be updated into B if and only if A is equal to this value.

According to the search pattern, BST is divided into an internal search tree and an external (leaf-oriented) search tree. The internal search tree maintains the value in the internal node, while in the external search tree, only the leaf node is stored with the actual key value, and internal nodes of the tree are used to guide a search operation along the path to the correct leaf. Our algorithm is based on a leaf-oriented search tree. Each internal node has only two children, which satisfies the following limitations: For each internal node x, the keys of all descendants in the left hand are less than x, and those of all descendants in the right hand are greater than or equal to the key of x.

Our BST implements the dictionary abstract data type and supports three operations: insert (k), delete (k), and contains (k). For convenience, we refer to the insert and delete operations as update operations.