A Simple Optimistic B-Skiplist Algorithm

arXiv:2610.37977 · cs.DS · Submitted 2026-10-27 · Read on arXiv

cs.DS

Submitted: 2026-10-27

Updated: 2026-10-27

License: http://creativecommons.org/licenses/by/4.0/

The gist: We present the first optimistic concurrent B-skiplist, built on optimistic lock coupling (OLC).

Abstract

We present the first optimistic concurrent B-skiplist, built on optimistic lock coupling (OLC). OLC replaces the multi-cache-line RW lock with a compact, single-cache-line lock: readers validate a version number without writing to shared memory, avoiding cache invalidations and retrying only on a detected conflict. Although OLC was thought poorly suited to skiplists, where a single per-element lock may span structurally unrelated levels, the B-skiplist's blocked layout places each level (and associated lock) in its own node. We exploit the B-skiplist's upfront knowledge of promotion height with a hybrid top-down scheme that traverses upper levels optimistically and locks only from the promotion level down, so most inserts never dirty a cache line. On 128 threads, the proposed optimistic B-skiplist achieves 1.2-10 times higher throughput over state-of-the-art concurrent skiplist implementations. Furthermore, the optimistic B-skiplist achieves 0.8-4.3 times the throughput compared to high-performance optimistic B+-tree implementations based on RW locks and OLC. Finally, the optimistic B-skiplist achieves up to 13 times lower latency than concurrent skiplists and tree-based indices, and is within 1.6 times of the latency of the OLC-based B+-tree.

Related papers