Concurrent Skip Lists

Skip lists are easier to make lock-free than red-black trees. The key tricks:

Per-node fine-grained locks: only lock the node being modified + its predecessors. Most operations affect a small set of nodes.

Lock-free with CAS:

• Insert: build the new node off-tree, then CAS-link it level-by-level from bottom up.
• Delete: mark forward pointers as logically deleted (using a tag bit on the pointer), then physically remove.

Java's ConcurrentSkipListMap is the canonical lock-free implementation. Used in everything from Cassandra to Akka.

Compared to lock-free B-trees: skip lists are simpler. The price is the memory overhead from extra pointers and the probabilistic worst case.

For most read-heavy workloads, a skip list with reader-writer locks is fine and far simpler than fully lock-free.