Bits & Bytes

Skiplists 101 - Understanding and Implementing Skiplists in Your Projects

Status: Ready Audience: Developers Illustrations: No Created time: January 3, 2025 12:42 PM Last edited time: January 12, 2025 11:05 AM

image.png

The World of Skiplists

The skiplist is a data structure that simplifies efficient data organization. This comprehensive guide explains how skiplists match the speed of balanced trees with a simpler design.

I became fascinated with skiplists while implementing a database storage engine. Even with a trivial implementation, this turned out to be a significant project. While I plan to write about that experience someday, I wanted to first share two elegant solutions for different workload challenges: the skiplist and the B+-tree. Most tutorials I found either simply paraphrased the original sources or lacked the depth needed for true understanding.

The skiplist is the simpler data structure to implement and it also has extenrive applications in the databases that I work with the most, so I’m covering that one first. We’ll probably need several articles later to cover B+-trees well.

To understand the basic operations, we'll use the analogy of finding a restaurant in a city with buildings of varying heights. After exploring this tasty analogy, we'll examine William Pugh's original implementation. You'll also discover why systems like Redis and LevelDB choose skiplists over B+ trees—another common database structure—for certain in-memory operations.

This guide covers skiplists from fundamentals to real-world usage, making it valuable for anyone interested in data structures, but most especially software developers looking to understand database internals.

At the end of the article you’ll find a helpful list of questions for you to test your understanding of this awesome data structure and ensure you’re ready to use it when the time comes.

What Is a Skiplist?

A skiplist is a randomized data structure that enables fast insertion, deletion, and search operations—averaging O(log n) time—without complex balancing. It consists of multiple stacked linked lists, where each higher level becomes sparser than the one below, serving as "express lanes."

• Level 0: The entire set of elements in a sorted linked list.

• Level 1+: Subsets of elements from previous levels, creating faster "skip" paths at higher levels.

Through random coin flips, elements get promoted to higher levels, naturally creating a balanced structure on average.

When introducing the skiplist in the original paper, the author wrote it as two words: skip list. Since then, papers have typically used one word: skiplist. We'll use the more modern spelling throughout the article.

Common Applications of Skiplists

The skiplist has been shown to be equivalent to a B-tree, so it can generally be used as a drop-in replacement. However, it’s better suited to high write throughput scenarios as it avoids the frequent rebalancing operations that slow down inserts in B-trees.

After its introduction, the skiplist became nearly as popular as the B-tree for data processing applications. Let’s take a look at some of the common scenarios where skiplists are used.

When you want to support high write throughput and range queries, a skiplist makes a great candidate.

Consider B-trees when IO is more important.

Dining on Delicious Deserts with Skiplists

Imagine each item in a list represented by a building on a street, with buildings rising to different heights. This row of buildings is like our skiplist. We'll explore how to traverse this structure using our imaginary jetpack.

Picture a restaurant on this street that makes the most amazing churros.

![image.png](assets/image 1.png)

Just like real streets, there are more short buildings than tall ones.

To find this mythical restaurant, you begin by jetpacking over buildings with lower addresses, quickly moving toward your tasty destination. Your jetpack lets you glide effortlessly across the tallest buildings.

When you spot a building taller than your destination's address, you descend one level where buildings are closer together. You continue skipping from rooftop to rooftop at this new height. Each time you encounter a building past the restaurant's address, you drop down again and check the next building's address at that lower level.

If you land exactly at your destination's address, you can drop straight down to the dining spot and place your order—by elevator, stairs, or jetpack, your choice.

You might need to walk past a few buildings at ground level, but you have a 50% chance of reaching your destination before touching the ground. The odds of walking past more than five buildings are just 1 in 100, and passing more than 10 buildings is a mere 1 in 3,000.

This is how search works in skiplists. Its efficiency comes from skipping numerous buildings by starting at higher levels.

![image.png](assets/image 2.png)

The same process for finding locations guides how we add (insert) and remove (delete) buildings—we first locate the exact spot, then simply update the connections.

Next we're going to get into the architecture of the skiplist data structure. And then we'll step through procedures for the basic operations: search, insert, and delete.

Understanding the Architecture

At the bottom (level 0), you have every element in a simple linked list. This is the same basic linked list you learned about in data structures—nothing fancy here.

![image.png](assets/image 3.png)

At higher levels, you'll find just one or two "sentinel" nodes. Think of your nodes as buildings that randomly grow to different heights. This randomness is crucial to the guarantees provided by the original skiplist, as described by William Pugh.

The structure consists of two main parts: a data layer at the bottom and index layers above it. Queries start at the index layers, either narrowing down the search range or finding the element directly, before ultimately reaching the data layer where the actual values are stored.

![image.png](assets/image 4.png)

The Core Principles

  1. Layered Linked Lists: Instead of one linked list, we have multiple (level 0, level 1, etc.).
  2. Randomization: Coin flips decide how many levels a new node occupies.
  3. Fast Search: Searching starts at the topmost (sparsest) list, moving right until you overshoot, then dropping down.

The Data Structure

A skiplist implementation requires a header structure that contains essential metadata:

struct Skiplist {
	head   *Node
	level  int
	size   int
}

The level field tracks the current maximum level in the skiplist, determined by the highest node. This level can increase when nodes are inserted (through random coin flips) or decrease when the last node at the highest level is deleted.

The size field counts the total elements in the skiplist, providing useful metadata for capacity monitoring and growth-based decisions.

The core of the structure lies in the Node definition:

struct Node {
	entry    *Entry
	forward  List[*Node]
	level    int
}

Let's examine the Node structure's components:

During insertion, we initialize a new node's forward array with pointers gathered during the search phase. These pointers maintain the skiplist structure across all levels where the node exists.

For deletion, we update the forward pointers of preceding nodes to bypass the deleted node at each level, preventing any dangling references.

The multi-level structure, managed through the forward array, enables efficient searching. Higher-level pointers serve as "express lanes," letting us skip many nodes during searches—similar to moving across the tops of taller buildings.

Finally, here's the straightforward Entry definition:

struct Entry {
  key    List[byte]
  value  List[byte]
}

The entry simply holds the indexing key and its associated value.

A Note About Probability

It’s true that you don’t need to know why the randomness of skiplists works to use them, but it helps build intuition for how the data structure works. With the compounding of a coin toss (assuming probability is 0.5), we are approximating a geometric distribution.

The likelihood of any node rising to some level is $p^{k-1}(1 - p)$ where $k$ is the level and $p$ is the probability. The expected number of levels for any node is $\frac{1}{1-p}$, which is $2$ for a probability of $0.5$. We can go farther showing that we expect 1/2 of nodes in level 1, 1/4 of nodes in level 2, 1/8 of nodes in level 3, and so on. This reveals the tree structure, which we’ll learn later makes the skiplist equivalent to B-trees.

In the end, the worst case performance of operations on a skiplist is $O(n)$, which is a far cry from the $O(\log n)$ opererations of a B+tree. However, this scenario means that no nodes appear in higher levels. The likelihood of this scenario is vanishingly small.

Let’s Talk Operations (With Original Pseudo-Code)

Let's walk through search, insertion, and deletion, each with pseudo-code adapted from William Pugh's original paper. This will give you a clear view of how these operations are formally defined. We'll start with search since both insert and delete operations build upon its logic.

The pseudo-code uses notation slightly modified from Pugh's original paper, though it stays true to his implementation. The code is straightforward and detailed enough to make translation to any programming language a simple task.

1. Searching

High-level idea

  1. Start at the highest level (e.g., level = listLevel).
  2. Move right while the next node's key is less than your search value.
  3. When you can't move right (to avoid overshooting), drop down one level.
  4. Repeat until you reach level 0 or find the exact node.

Beyond our earlier jetpack analogy, think of this progressively refined search like traveling from DC to a restaurant in Manhattan. First, an express train rockets you to Union Station with minimal stops. Then a local train, stopping every few blocks, gets you near your destination. An Uber, stopping at traffic lights, brings you within a block. Finally, you walk door-to-door to find your spot.

And there you are at the dining spot with those tempting churros. Quite a journey for dessert—they must be spectacular!

For a more formal perspective, imagine a decision tree where each level adds detail to the one above. Whether to continue at the current level or drop down depends on if the next node's value exceeds your search target.

![image.png](assets/image 5.png)

Here's the Pseudo-code (Adapted from Pugh's Paper):

function SEARCH(list, searchKey):
	node := list.header       // Start at "header" (sentinel) at top level
	// loop invariant: x.key < searchKey
	for i := list.level downto 1 do:
		while node.forward[i].key < searchKey do:
			node := node.forward[i]
	// assert: node.key < searchKey <= node.forward[i].key
	node := node.forward[i]
	if node.key == searchKey then
		return node.value
	else
		return NULL

Let's break down how this search works in the code.

Now that we've covered searching, we'll build on this pattern with inserting and deleting. Let's explore inserts, where the skiplist truly shines.

2. Inserting

Now that we understand searching in a skiplist, let's explore adding new elements. Insertion builds on our search method with a key addition: as we search, we track potential pointer update locations for the new node. This tracking is crucial since we'll need to reconnect the skiplist at multiple levels.

Think of insertion as finding a spot in line while remembering everyone who needs to know about the newcomer at each "express lane" level. While this may sound complex, skiplist insertion is surprisingly elegant in practice.

High-level idea

  1. Search for the new element's position using our search method, but track the nodes where we stop at each level (these become our "update pointers").
  2. Insert the new node at level 0.
  3. Flip a coin to decide whether to promote the node to level 1. If heads, link it at level 1 using the saved update pointers.
  4. Continue flipping coins and promoting until you get tails or reach MAX_LEVEL.

To determine a new key's level, we generate a random level value. This approach creates a probability distribution where higher levels become increasingly rare. We use 0.5 as our probability—both for the simplicity of describing it as coin flips and because this was the value in the original paper. The paper also discusses how to select different probabilities and analyzes their impact on time and space complexity.

The skiplist's structure depends solely on the number of elements and the random number generator. Here's the code for selecting a level:

function RANDOM_LEVEL():
	lvl := 1
	// rand() is a uniformly distributed random number in [0..1)
	while rand() < PROBABILITY and lvl < MAX_LEVEL do
		lvl := lvl + 1
	return lvl

With our level selection method in place, let's examine the insertion process. The INSERT function combines our searching strategy with random level selection to add new nodes. It maintains the skiplist's structure by carefully updating pointers at each level.

function INSERT(list, searchKey, newValue):
	update[1..MAX_LEVEL]     // Array of pointers to track where to insert at each level
	node := list.header
	// 1. Search through levels top-down to find position of 'searchKey'
	for i := list.level downto 1 do:
		while node.forward[i].key < searchKey do:
			node := node.forward[i]
		// assert: node.key < searchKey <= node.forward[i].key
		update[i] := node
	// 2. Move to level 1
	node := node.forward[1]
	// 3. If 'key' not found, we insert a new node
	if node.key == searchKey then
		node.value := newValue
	else:
		// 3a. Randomly generate newLevel
		newLevel := RANDOM_LEVEL()
		if newLevel > list.level then
			for i := list.level+1 to newLevel do:
				update[i] := list.header
			list.level := newLevel
		// 3b. Create new node
		newNode := new Node(newLevel, searchKey, newValue)
		// 3c. Initialize forward references and insert
		for i := 1 to newLevel do:
			newNode.forward[i] := update[i].forward[i]
			update[i].forward[i] := newNode

Let's break down the key points of this insertion code:

Next, we'll explore deletions, which follow a similar pointer-tracking process across all levels.

3. Deleting

![image.png](assets/image 6.png)

After mastering insertion, deletion follows a similar but reversed pattern. Rather than adding connections at various levels, we carefully remove them while maintaining the skiplist's structure. The process requires attention to avoid dangling pointers or gaps in our express lanes. Let's examine how it works.

High-level idea

  1. Just like insertion, we perform a top-down search, tracking nodes at each level using update[].
  2. Once we find the target node (if it exists), we remove its references at every level.
  3. If we removed something at the highest level and that level becomes empty, we decrease list.level.

Pseudo-code (Adapted from Pugh's Paper)

function DELETE(list, searchKey):
	update[1..MAX_LEVEL]
	node := list.header
	// 1. Find node and keep track of update positions
	for i := list.level downto 1 do:
		while node.forward[i].key &lt; searchKey do:
			node := node.forward[i]
			update[i] := node
	// 2. Potential candidate
	node := node.forward[1]
	// 3. If we found the key, remove it from each level
	if node.key == searchKey:
		for i := 1 to list.level do:
			if update[i].forward[i] != node then break
		update[i].forward[i] := node.forward[i]
		free(node)
		// 4. Adjust list.level if highest level is now empty
		while (list.level &gt; 1) and (list.header.forward[list.level] == NIL) do:
			list.level := list.level - 1

Memory Requirements

With multiple levels, a skiplist has a constant-factor overhead compared to a single linked list. When the probability of promotion is 1/2, each element appears in about 2 levels on average. This means the total space is about 2n for n items, which remains O(n). However, the extra pointer arrays in each node create more overhead than a plain single linked list.

Time Complexity Shenanigans

Because the height of a skiplist is $O(\log n)$ on average (due to random coin flips), operations—search, insert, and delete—will typically run in $O(\log n)$. While the worst-case time is $O(n)$ if you get extremely unlucky coin tosses (i.e., every node promotes to the max level), that’s astronomically unlikely. Life’s short, so we’ll take those odds, when other tradeoffs of the skiplist make sense.

Why Use Skiplists?

![image.png](assets/image 7.png)

Skiplists vs. B+ Trees

It’s been shown that skiplists are functionally and structurally equivalent to B-trees. Structural equivalence means that adjacent items in one structure will also be adjacent in the other. And functional equivalence means that that the worst-case cost functions are in the same big-O order of complexity.

Let’s look at some of the tradeoffs that inform when we should use skiplists and when we should use B-trees.

  1. Use Cases & Storage
  1. Balancing & Complexity
  1. Memory
  1. Performance
  1. Concurrency

Putting It All Together

A skiplist maintains multiple levels of linked lists, with nodes potentially appearing across multiple levels. Random coin flips determine each node's "height," naturally balancing the structure and providing O(log n) search, insert, and delete times—all with much simpler implementation than balanced trees.

For disk-stored data where you need to minimize page reads, a B+ tree is your best bet. But for in-memory operations, simple implementation, or concurrency-friendly needs, a skiplist shines.

Final Thoughts

Skiplists elegantly combine randomness with linked list simplicity to create a worthy alternative to trees. And hey, they make for great party conversation—just flip a coin to pick your next victim!

So go forth, armed with:

  1. The skiplist concept (stacked linked lists).
  2. Random coin toss insertion logic.
  3. Pseudo-code from the original paper, radiating academic brilliance.

May your coin flips be favorable, and may you never face the $O(n)$ walk of shame again.

Summary

![image.png](assets/image 8.png)

Additional Reading

There’s much more to skiplists, especially the many specializations, that we didn’t cover. These are the sources that I found most helpful in my journey to understanding them.

Review Questions

These are review questions that I used to retain the key facts of skiplists.

Questions

  1. What is the primary advantage of using a skiplist over a balanced tree structure like AVL or Red-Black trees?
  2. How is the height of a node determined in a skiplist?
  3. What is the average time complexity for search, insert, and delete operations in a skiplist?
  4. Why are skiplists particularly well-suited for concurrent implementations?
  5. What is the space complexity of a skiplist, and how does it compare to a regular linked list?
  6. What role does the update[] array serve in skiplist operations?
  7. In what scenarios would you choose a B+ tree over a skiplist?
  8. What is the worst-case time complexity of skiplist operations, and why is it rarely a concern?
  9. How does a skiplist maintain its balance?
  10. What happens to list.level during delete operations?

Answers

  1. skiplists offer simpler implementation without complex rotations, relying instead on random promotion for balance.
  2. The height is determined through random coin flips (or similar randomization), where each level has a probability (often 1/2) of promoting to the next level.
  3. The average time complexity is $O(\log n)$ for all three operations.
  4. skiplists are easier to implement in concurrent scenarios because they don't require complex rebalancing operations, making both lock-free and lock-based implementations simpler than with balanced trees.
  5. A skiplist has $O(n)$ space complexity but with a larger constant factor - typically about $2n$ for n items when using 1/2 promotion probability.
  6. The update[] array keeps track of the nodes at each level that need to be modified during insert and delete operations, storing the last node examined at each level.
  7. B+ trees are preferred for disk-based storage and when optimizing for minimal disk I/O, such as in databases and file systems.
  8. The worst-case is $O(n)$, but it's astronomically unlikely due to requiring extremely unfavorable random coin flips where every node promotes to the maximum level.
  9. Balance is maintained probabilistically through random promotion of nodes to higher levels, without explicit rebalancing operations.
  10. If nodes are deleted from the highest level and that level becomes empty, list.level is decremented to maintain an efficient structure.