Skip list

Deep dive

How it works

In: a key (and a value on insert) · Out: the value or absent; iteration in key order · State: a tower of forward pointers per node, heights drawn at random (p = 1/4) · Cost: O(log n) expected, about 2·log2 n comparisons, 1.33 pointers per node

L2: head ----------------------> 30 -----------------> nil
L1: head -------> 10 ----------> 30 -------> 50 ------> nil
L0: head -> 5 -> 10 -> 20 -> 25 -> 30 -> 40 -> 50 -> 60 -> nil
search 40: L2 to 30, L1 30 -> (50 too big) drop, L0 30 -> 40 found

1. Search(k): from the head at the top level, advance while next.key < k; record the node as preds[level]; drop a level. At level 0, preds[0].next is the candidate.
2. Insert(k, v): compute preds; if the key exists, update. Pick height h geometrically with parameter p. Set node.next[l] = preds[l].next[l], then preds[l].next[l] = node for l < h (bottom up, so the node is reachable at level 0 first).
3. Delete: compute preds; set preds[l].next[l] = node.next[l] for each of the node's levels (top down for concurrent readers).
4. Range scan: search the start key, then follow level 0.

Code

// Arena-backed skip list (indices instead of pointers, no unsafe). p = 1/4.
const MAX_LEVEL: usize = 12;
const NIL: u32 = u32::MAX;

struct Node<K, V> { key: K, val: V, next: Vec<u32> } // next[l] = successor on level l

pub struct SkipList<K: Ord, V> { nodes: Vec<Node<K, V>>, head: [u32; MAX_LEVEL], level: usize, rng: u64 }

impl<K: Ord, V> SkipList<K, V> {
    pub fn new() -> Self { SkipList { nodes: Vec::new(), head: [NIL; MAX_LEVEL], level: 1, rng: 0x9E37_79B9_7F4A_7C15 } }

    fn succ(&self, p: Option<u32>, l: usize) -> u32 {
        match p { None => self.head[l], Some(i) => self.nodes[i as usize].next[l] }
    }
    // preds[l] = last node on level l with key < k (None = head).
    fn preds(&self, k: &K) -> [Option<u32>; MAX_LEVEL] {
        let mut preds = [None; MAX_LEVEL];
        let mut p = None;
        for l in (0..self.level).rev() {
            loop {
                let n = self.succ(p, l);
                if n != NIL && self.nodes[n as usize].key < *k { p = Some(n) } else { break }
            }
            preds[l] = p;
        }
        preds
    }
    fn random_level(&mut self) -> usize {
        self.rng ^= self.rng << 13; self.rng ^= self.rng >> 7; self.rng ^= self.rng << 17;
        // P(level > j) = 4^-j: two trailing zero bits per extra level
        (self.rng.trailing_zeros() as usize / 2 + 1).min(MAX_LEVEL)
    }

    pub fn get(&self, k: &K) -> Option<&V> {
        let n = self.succ(self.preds(k)[0], 0);
        (n != NIL && self.nodes[n as usize].key == *k).then(|| &self.nodes[n as usize].val)
    }

    pub fn insert(&mut self, k: K, v: V) {
        let preds = self.preds(&k);
        let n = self.succ(preds[0], 0);
        if n != NIL && self.nodes[n as usize].key == k { self.nodes[n as usize].val = v; return; }
        let h = self.random_level();
        self.level = self.level.max(h); // preds above the old level are None = head, which is right
        let id = self.nodes.len() as u32;
        let next = (0..h).map(|l| self.succ(preds[l], l)).collect();
        self.nodes.push(Node { key: k, val: v, next });
        for l in 0..h { // bottom-up: a concurrent reader would see the node on level 0 first
            match preds[l] { None => self.head[l] = id, Some(p) => self.nodes[p as usize].next[l] = id }
        }
    }

    pub fn range_from<'a>(&'a self, k: &K) -> impl Iterator<Item = (&'a K, &'a V)> + 'a {
        let mut cur = self.succ(self.preds(k)[0], 0);
        std::iter::from_fn(move || {
            if cur == NIL { return None; }
            let n = &self.nodes[cur as usize];
            cur = n.next[0];
            Some((&n.key, &n.val))
        })
    }
}

Complexity and constants

• Expected search cost (1/p)·log_{1/p} n steps: p = 1/2 and p = 1/4 both give about 2·log2 n comparisons; p = 1/4 uses fewer pointers (1.33 vs 2 per node).
• Space: key + value + 1/(1-p) pointers + allocation header; with per-node Vec as above, add 24 bytes; real implementations allocate node and tower inline (variable-size node).
• Out-of-cache lookup: about 1 cache miss per visited node below the cached top levels; at 10^7 keys order of 15-30 misses, order of 1-3 µs. A B+ tree with 256-byte nodes takes 4-6 misses.
• Insert: search + one allocation + h pointer writes.

Efficiency

• Cost: every step is a dependent load: at 10^7 keys about 15-30 cache misses, order of 1-3 µs per lookup out of cache, against 4-6 misses for a B+ tree with 256-byte nodes. Memory is key + value + 1.33 pointers per node (p = 1/4) plus allocation header. Bound: memory latency (pointer chasing).
• Levers:
  • inline towers in one block — key and low pointers share a cache line, no separate Vec (LevelDB NewNode) — all production use
  • arena allocation, never free until the table dies — no per-node malloc, no reclamation needed (LevelDB memtable) — write-once memtables
  • single writer with release/acquire on next pointers — readers take no lock (LevelDB) — one writer thread
  • p = 1/4 instead of 1/2 — 1.33 instead of 2 pointers per node at the same comparison count (Pugh 1990) — always
  • start at the current max level and keep a search finger — fewer levels walked (order of) — sequential or clustered keys
• Naive → standard → state of the art:
  • sorted linked list · O(n) per search
  • skip list, p = 1/4 · 2·log2 n comparisons, 1.33 pointers per node
  • inline-tower lock-free skip list (RocksDB InlineSkipList) or, single-threaded, a B+ tree / ART · several times fewer misses

Implementation notes

• Inline towers: allocate Node { key, val, height, next[height] } in one block (LevelDB NewNode uses an arena and sizeof(atomic<Node*>) * (height-1) extra bytes). One cache line holds the key and the lower pointers.
• Single-writer concurrency (LevelDB memtable): writer fills node.next[l] with relaxed stores, then publishes with preds[l].next[l].store(node, Release); readers use load(Acquire). Nodes are never freed while the memtable lives, so no reclamation is needed.
• Multi-writer lock-free (Fraser, ConcurrentSkipListMap, RocksDB InlineSkipList concurrent insert): CAS on each level's predecessor, bottom-up; delete marks the node's next pointers (low bit) first, then unlinks. Needs epoch-based reclamation or hazard pointers to free nodes.
• Rank/indexable skip list (Redis): store a span (number of level-0 nodes skipped) with each forward pointer; rank and select become O(log n).
• Cache the height of the list; start searches at the current max level, not MAX_LEVEL.
• Use a fast thread-local RNG; one xorshift per insert is enough.

Pitfalls

• Comparing with <= vs < in the search loop decides whether duplicates go before or after equals; be consistent between insert and delete.
• In concurrent designs level 0 defines membership (the linearization point): link it first on insert, unlink it last on delete, or searches can disagree about whether a key is present.
• Unbounded height from a bad RNG (e.g. the same seed per thread producing tall towers together).
• Freeing deleted nodes immediately in a concurrent skip list: readers may still be traversing them.
• Benchmarking with sequential keys in cache hides the pointer-chasing cost.

Variants and alternatives

In production

• Databases and storage engines: LevelDB and RocksDB memtables (RocksDB InlineSkipList, max height 12, branching 4), Apache HBase memstore (via ConcurrentSkipListMap), SingleStore (lock-free skip-list indexes).
• In-memory data stores: Redis sorted sets (zskiplist, p = 0.25, max level 32, with spans for ZRANK).
• Language runtimes: Java ConcurrentSkipListMap.
• Search engines: Lucene writes multi-level skip lists into postings lists to jump over document ids (Lucene docs).

Implementations

Sources

• William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Communications of the ACM 33(6), 1990. paper
• Keir Fraser, Practical Lock-Freedom, PhD thesis, University of Cambridge, 2004 (UCAM-CL-TR-579). pdf
• Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, chapter 14 (skip lists), 2008.
• LevelDB source, db/skiplist.h. code
• RocksDB source, memtable/inlineskiplist.h. code