Skip Lists and Expected Logarithmic Index Operations
A skip list is a sorted linked list with additional linked-list layers that let algorithms jump over many items at once. Each stored item appears in the bottom list, while some items also appear in progressively higher lists. Randomly choosing how many layers each item occupies gives search, insertion, and deletion an expected O(log n) time cost.
The problem: ordered data with fast updates
An ordered index stores keys in sorted order so it can find a key, walk through a range, or locate the first key greater than a target. A plain linked list is easy to update: inserting an item only requires changing a few pointers. But finding the insertion point requires walking from the beginning, which costs O(n) in the worst case.
An array has the opposite trade-off. Binary search finds a key quickly, but inserting or deleting in the middle usually requires shifting many elements. A balanced search tree avoids both problems, but its rotations and rebalancing rules make the implementation more involved.
A skip list keeps the simple pointer-based updates of a linked list and adds shortcuts for searching.
One list becomes several layers
The bottom layer contains every item in sorted order. Above it are shorter linked lists containing selected items from the layer below. Each higher-layer pointer skips over a larger section of the data.
For example, the bottom layer might contain every key:
1 -> 4 -> 7 -> 9 -> 13 -> 18 -> 21 -> 25
A higher layer could contain every few of those keys:
1 --------> 7 --------> 13 --------> 21
The top layer might contain only:
1 -------------------------------> 13
These are not separate copies of unrelated records. A node for a key owns a sequence of forward pointers, one for each layer in which it participates. A node with three pointers appears in layers 0, 1, and 2; a node with one pointer appears only in the bottom layer.
Implementations commonly add a sentinel head node, a dummy node before the smallest key. It has pointers for every possible layer and avoids special cases when an operation starts at the beginning of the list. The list also tracks its current highest nonempty layer.
Searching from the top down
To search for a key, start at the sentinel in the highest layer. Look at the next node:
- If its key is less than the target, move forward in the current layer.
- If its key equals the target, the search is complete.
- If its key is greater than the target, drop down one layer without moving forward.
At each layer, the algorithm advances while it can safely remain before the target. When it reaches the bottom layer, the next node is either the target or the first key greater than it.
The same procedure can find an insertion point or the beginning of a range. A search for 15, for example, may use a high-level pointer to pass 1, 4, 7, and 13, then descend and inspect the smaller gap between 13 and 18.
The important property is that the algorithm does not restart from the beginning at each layer. It carries its current position downward, refining the search area.
Insertion records the search path
To insert a new key, search for it as usual, but record the last node visited at each layer. These nodes are the new node's predecessors—the nodes that should point to it after insertion.
Suppose the new key belongs between 13 and 18. At the bottom layer, the predecessor is 13. At a higher layer, the predecessor might also be 13, or it might be an earlier node if that layer skips over the insertion point.
Next, choose the new node's height: the number of layers in which it will appear. The implementation makes this choice randomly, often by repeatedly flipping a biased coin: include the node in the next layer with probability p, commonly one-half, and stop when the trial fails or a configured maximum is reached.
For every layer below the chosen height, insertion changes two pointers:
- The new node points to the predecessor's former successor.
- The predecessor points to the new node.
Because the list is linked rather than stored contiguously, no existing records need to move. The new node's key remains in sorted order in every layer where it appears.
Deletion uses the same path
Deletion first searches for the target and records the predecessors. If the target is absent, nothing changes. If it exists, then for each layer containing that node, the predecessor's pointer is changed to skip over the node and point to its successor.
Afterward, empty top layers can be removed from the list's recorded height. The node itself can then be reclaimed by the language runtime or memory-management scheme. As with insertion, no neighboring records need to shift.
Why random heights produce logarithmic performance
Randomization prevents the upper layers from becoming predictably crowded in one area. With promotion probability p, about p of the nodes reach layer 1, about p² reach layer 2, and about p³ reach layer 3. Each layer is therefore expected to contain a constant fraction of the nodes in the layer below.
A search moves forward only a limited number of times per layer before dropping down. It also visits only about log n layers on average, because the expected number of nodes reaching a given height shrinks exponentially. The expected total work is therefore O(log n) for search, insertion, and deletion.
This is an expected bound, not an absolute guarantee. An unlucky sequence of random choices could give many nodes large heights, or leave the structure with a long sparse region. In the extreme, an operation can take O(n) time. Implementations usually cap the maximum height, which bounds memory use but does not turn the general worst-case operation into a strict logarithmic guarantee.
A skip list uses expected O(n) node-pointer storage. Its bottom layer also makes ordered iteration and range scans straightforward: find the first key in the range, then follow bottom-layer pointers until the endpoint.
When a database log, configuration option, or incident report mentions a skip-list index—often in the context of an in-memory table or ordered set—it is describing this trade-off: simple pointer updates and efficient ordered access, with logarithmic performance arising from probability rather than tree rebalancing.