The Practical Guide to Skiplist Data Structure (No Fluff)

For most of my career, I viewed skiplists as a niche data structure—the kind of thing you study in a computer science elective, admire for its cleverness, and then promptly forget because binary search trees or balanced trees usually get the job done. They have a cult following, sure, but they often feel like a solution in search of a problem. That changed when we hit a wall at Antithesis. We needed to traverse massive branching trees of execution timelines, and standard database approaches were failing us.

If you’re working with large-scale data, you know the pain of point lookups in analytic databases. We were using BigQuery, which is fantastic for scanning massive datasets in parallel but abysmal at fetching specific rows by ID. Representing a tree with simple parent pointers meant that every step up the tree required a new lookup. In a deep tree, you’re looking at O(depth) reads, which is a performance killer. You might think about splitting your data into two systems, but that introduces the nightmare of maintaining consistency across distributed writes. I’d rather avoid two-phase commit protocols whenever possible.

This is where the humble skiplist becomes a superpower. A skiplist is essentially a linked list with "express lanes." By promoting nodes probabilistically to higher levels, you turn an O(n) search into an O(log n) operation. But how do you apply that to a tree? We invented what we call a "skiptree."

A skiptree is essentially a hierarchy of trees layered on top of each other. You take your base tree (level 0) and create higher-level trees where each node has a 50% chance of being promoted. If you trace any path from root to leaf, you’re effectively traversing a skiplist. To implement this in SQL, you create a table for each level. Instead of a single parent pointer, each row stores a next_level_ancestor and an ancestors_between column containing the nodes you skipped over.

Here is the beauty of this approach: you can find the ancestors of any node using a single, non-recursive SQL query with a fixed number of joins. You start at the bottom, jump to the ancestor in the next level up, collect the nodes you skipped, and repeat until you hit the root.

Why does this matter for your architecture?

• Predictable Performance: You replace recursive lookups with a fixed number of joins, keeping your query costs stable.
• Database Agnostic: You don't need a specialized graph database to handle tree traversal; standard SQL tables work perfectly.
• Scalability: Because you’re using a geometric distribution of table sizes, the cost of these queries remains surprisingly low even as your tree grows.

Most engineers get tripped up by trying to force tree structures into flat tables using standard recursive CTEs, which can be incredibly slow on massive datasets. By pre-calculating the "express lanes" using a skiptree, you shift the complexity from query time to write time. It’s a classic trade-off, but when you’re dealing with millions of nodes, it’s the only way to keep your system responsive.

If you’re struggling with tree traversal performance in an analytic database, stop trying to optimize the query and start optimizing the data structure. Have you ever had to build a custom data structure to solve a database bottleneck? Try this today and share what you find in the comments.