Many systems need an in-memory structure that keeps keys sorted while still supporting fast reads, writes, range scans, and iteration.

A Skip List is a sorted linked list with extra shortcut lanes above it. Those lanes let searches jump over large parts of the list instead of walking one node at a time.

Updates usually touch only a small area of the list. That makes skip lists simpler to implement and often easier to make concurrent than many balanced trees.

The trade-off is that skip-list performance depends on randomness. In normal use, operations are expected to be O(log n), but skip lists do not give a strict worst-case guarantee.

This chapter explains how skip lists are structured, how search, insert, and delete work, why they fit concurrent systems, and how they compare to balanced trees.

Consider an in-memory index for a storage engine. New writes arrive continuously. Reads need to find individual keys. Flushes need to scan keys in sorted order before writing read-only files to disk.

The structure needs fast get(key), put(key, value), delete(key), and scan(start_key, end_key) operations.

A plain linked list keeps sorted order, but search is linear:

A balanced tree gives O(log n) operations, but inserts and deletes may rotate nodes to keep the tree balanced. That is fine in many systems. It gets harder when several threads update the structure at the same time, range scans need a stable sorted path, the implementation must stay small enough to review, or the structure sits on a hot write path.

Skip lists take a different approach: instead of balancing with rotations, they use randomness to build shortcut lanes.