Skip Lists: Probabilistic Multi-Level Indexing & O(log N) Search Proof

Probabilistic Express Lanes & The Backwards Search Proof

In a sorted singly linked list, even though the keys are ordered, binary search is impossible because we lack random access. Suppose we construct a hierarchy of linked lists $L_0, L_1, \dots, L_{H}$: level $L_0$ contains all $N$ elements, and each element present in level $L_k$ is independently promoted to level $L_{k+1}$ with probability $p \in (0, 1)$ (typically $p = 1/2$ or $p = 1/4$). Search starts at the highest level of the sentinel head node: at the current node $u$ and level $k$, we advance horizontally (u = u->forward[k]) as long as u->forward[k]->key < target; when the next key would overshoot target (or is nullptr), we drop down vertically to level $k - 1$.

How do we prove that the expected search cost is $O(\log N)$? Follow Pugh's elegant Backwards Analysis: trace the search path in reverse, starting from the found node at level $0$ and climbing up and left back to the sentinel head at level $H$. At any node on the reverse path at level $k$:

• Did we arrive at this node by dropping down from level $k+1$? That happens if and only if this node's tower was promoted to level $k+1$, which occurs with probability $p$ (we climb UP 1 level).
• Otherwise, with probability $1 - p$, this node's tower stopped at level $k$, so the forward search must have reached it horizontally from the left (we step LEFT 1 node at level $k$).

Skip List Parameter Trade-Offs ($p = 1/2$ vs. $p = 1/4$ vs. Balanced BSTs)

Visualizing Express Lanes & The update[0..level] Predecessor Splice Vector

Why RocksDB & Java ConcurrentSkipListMap Use Skip Lists Over Red-Black Trees

Production Implementation: Single-Allocation Skip List with $p = 1/4$ Geometric PRNG

#include <array>
#include <cstdint>
#include <cstdlib>
#include <new>

class SkipList {
  static constexpr int MAX_LEVEL = 16; // Supports up to 4^16 = 4.29B elements

  struct Node {
    int key;
    int value;
    int top_level;
    Node* forward[1]; // Flexible trailing array allocated to size top_level + 1
  };

  Node* head_;
  int cur_max_level_ = 0;
  std::uint64_t rng_state_ = 0x853c49e6748fea9bULL;

  static Node* allocate_node(int key, int val, int level) {
    const std::size_t bytes = sizeof(Node) + static_cast<std::size_t>(level) * sizeof(Node*);
    void* raw = ::operator new(bytes);
    Node* node = static_cast<Node*>(raw);
    node->key = key;
    node->value = val;
    node->top_level = level;
    for (int i = 0; i <= level; ++i) node->forward[i] = nullptr;
    return node;
  }

  // Fast xorshift64* PRNG sampling Geometric(p = 1/4) height
  int random_level() noexcept {
    int lvl = 0;
    while (lvl < MAX_LEVEL - 1) {
      rng_state_ ^= rng_state_ >> 12;
      rng_state_ ^= rng_state_ << 25;
      rng_state_ ^= rng_state_ >> 27;
      if (((rng_state_ * 0x2545F4914F6CDD1DULL) >> 62) != 0) break; // 1/4 probability
      ++lvl;
    }
    return lvl;
  }

public:
  SkipList() {
    head_ = allocate_node(-2147483648, 0, MAX_LEVEL - 1);
  }

  const int* find(int target) const noexcept {
    const Node* curr = head_;
    for (int i = cur_max_level_; i >= 0; --i) {
      while (curr->forward[i] != nullptr && curr->forward[i]->key < target) {
        curr = curr->forward[i];
      }
    }
    curr = curr->forward[0];
    if (curr != nullptr && curr->key == target) return &curr->value;
    return nullptr;
  }

  void insert(int key, int value) {
    std::array<Node*, MAX_LEVEL> update{};
    Node* curr = head_;

    for (int i = cur_max_level_; i >= 0; --i) {
      while (curr->forward[i] != nullptr && curr->forward[i]->key < key) {
        curr = curr->forward[i];
      }
      update[i] = curr;
    }

    curr = curr->forward[0];
    if (curr != nullptr && curr->key == key) {
      curr->value = value;
      return;
    }

    const int new_lvl = random_level();
    if (new_lvl > cur_max_level_) {
      for (int i = cur_max_level_ + 1; i <= new_lvl; ++i) {
        update[i] = head_;
      }
      cur_max_level_ = new_lvl;
    }

    Node* inserted = allocate_node(key, value, new_lvl);
    for (int i = 0; i <= new_lvl; ++i) {
      inserted->forward[i] = update[i]->forward[i];
      update[i]->forward[i] = inserted;
    }
  }
};