TL;DR: Concurrent binary search trees are notoriously hard to implement correctly. This paper introduces "logical ordering" -- separating the logical key order from the physical tree structure -- enabling safe concurrent operations without complex tree rotations under locks.
The Problem
Binary search trees (BSTs) are fundamental data structures, but making them work correctly under concurrent access is extremely challenging. When multiple threads insert, delete, and search simultaneously, tree rotations needed for balancing conflict with concurrent traversals. A thread performing a rotation might redirect pointers that another thread is currently following, leading to lost nodes, corrupted structure, or incorrect search results.
Existing approaches either use coarse-grained locking (serializing all operations, killing performance) or attempt fine-grained schemes that are notoriously difficult to get right. The fundamental tension: structural changes (rotations) affect the very paths that concurrent operations traverse.
The Key Idea: Logical Ordering
The central insight is to decouple the logical correctness of the data structure from its physical tree shape. The paper maintains two representations simultaneously:
- The physical BST -- used for fast O(log n) traversals to locate nodes.
- The logical ordering -- a linked list threading through nodes in key order, serving as the ground truth for which keys are in the set.
Searches use the tree structure for speed but validate against the logical order. Insertions and deletions synchronize on the logical ordering (the linked list), not on the tree structure. This means rotations can happen concurrently with searches without breaking correctness -- a search that gets "lost" due to a rotation simply falls back to the logical order.
Interactive Demo
Concurrent BST with Logical Ordering
Choose a scenario and click Run to watch two threads ( Thread A and Thread B) operate concurrently on the BST. The tree (top) and the logical ordering linked list (bottom) update independently.
Naive Approach
Logical Ordering
How It Works
The Logical Ordering Invariant
Every node in the tree maintains predecessor and successor pointers forming a sorted linked list. This list is the authoritative record of set membership. A node is considered "in the set" if and only if it is reachable via the logical ordering list -- even if the tree pointers have been temporarily redirected by a concurrent rotation.
Lock-Free Searches
Search operations are entirely lock-free. A search traverses the tree using standard BST navigation. When it reaches a candidate node, it validates the result by checking the logical ordering: is the node still linked in the sorted list? If a concurrent rotation moved pointers during the traversal, the search simply checks the logical order to confirm correctness. No locks, no retries, no complex helping mechanisms.
Fine-Grained Locking for Mutations
Insert and delete operations use fine-grained locking -- but only on the logical ordering, not on tree structure. To insert a key, a thread:
- Traverses the tree (lock-free) to find the insertion point.
- Locks the predecessor and successor in the logical ordering.
- Validates the locked nodes are still adjacent in the list.
- Inserts the new node into both the logical list and the tree.
- Releases locks.
Because rotations only affect tree pointers (not the logical list), they can proceed concurrently with mutations on different parts of the tree without interference.
Results
The logical ordering approach outperforms existing concurrent BSTs -- including lock-free skip lists and lock-based AVL trees -- in throughput across a range of workloads. It achieves near-linear scalability on multi-core machines while maintaining the O(log n) expected depth of balanced BSTs. The key advantage: by reducing the critical section to logical list manipulation (a constant-time pointer update), contention is minimized even under heavy concurrent load.