I have a passion for storage engine design and I usually like to clone my own version like Redis, LevelDB, ... These projects require knowledge about awesome data structures and Skip List is not an exception. That's the reason why I built my own Skip List in C++ here (Of course implemented without AI, but not the unit tests, LMAO, please give it a star!) and I want to write a blog to share what I've learned. Let's read and increase your knowledge!
01Introduction
The problem is: "How can you perform a O(log(n)) search, insert and delete without tree rotation (which can be faster but more complex as well)"? Skip List was created to support this case by William Pugh in 1989. You can reference this paper: Skip Lists: A Probabilistic Alternative to Balanced Trees (the linked PDF is the CACM version, published June 1990).
It is now commonly used in well-known applications:
(ZSET)02Why sorted linked list isn't enough?
If the objective is just a simple search data structure, only a sorted linked list is enough, right? But there are several drawbacks that need to be considered carefully.
That's the scenario "Skip List" was created for.
03The core idea: Express Lanes
Let's think of Skip List basically as an express lane visualized below, where local trains stop at every station (lane with level 0) and express trains skip stations (level 1+).
Searching and Inserting = ride the express as far as you can and drop down a level, repeatedly.
04Structure definition
key and an array next[0...level] of next pointers - so a node sitting at level L owns L + 1 lanesMAX_LEVEL - indicates the max level, which is the maximum number of express lanes; Redis uses 32, the real C++ caps at 17, because at P = 1/4 seventeen lanes already reach ~4^16 (~4 billion) elements and a taller header buys nothing past thatP - probability of promoting a node to the next level (0.5 or 0.25 typically, meaning the next level contains two or four times fewer elements) => Trade-off: P smaller => fewer lanes, less memory, but less efficient search/insertpseudocode
// Convention for every block below: a level is a 0-based lane INDEX, never a
// lane count, and every "for i = a to b" range is INCLUSIVE of b. Mixing the
// two is the single easiest way to break a skip list.
struct Node {
K key
V value
int level // this node's top lane index
Node* next[] // lanes 0..level, so length = level + 1
}
struct SkipList {
Node* header
int level // index of the highest lane currently in use
float P
int MAX_LEVEL
}
See the real C++ Node in skip_list_impl.h and the SkipList surface in skiplist.h - they live in separate files, because the public class is a pimpl holding nothing but a unique_ptr to a private Impl. It's like concept of private implementation
That next[] in the pseudocode is literal, and it is the one place the C++ stops looking like C++. A node is a single allocation: the code asks for sizeof(Node) + sizeof(Node*) × level bytes and placement-news the value into the front of it, so the value, the height and every lane pointer share one block and there is exactly one operator new per element. Level is a std::uint8_t for the same reason - it sits in every node, and a lane index never exceeds MAX_LEVEL - 1, so for a small T a wider counter would cost more per element than the value does.
05Operations (with pseudocode)
5.1Random level
The whole idea of this data structure is how to define a sufficient level-randomisation algorithm for all cases. So, how do we determine the level of the inserted node? In most cases, we use a simple probability function utilizing P and MAX_LEVEL to determine it. Pseudocode below:
pseudocode
PROMOTE_THRESHOLD = P × 2^32 // precomputed; for P = 1/4 this is 2^30
function fastRand(n):
return (n × 1664525 + 1013904223) mod 2^32
// Returns a 0-based top INDEX, not a lane count. Returning 0 is the common
// case - it happens with probability 1 - P, and it means "lane 0 only".
function randomLevel(rnd): // rnd passed by reference, carries state
level = 0
rnd = fastRand(rnd)
while rnd < PROMOTE_THRESHOLD and level < MAX_LEVEL - 1:
level = level + 1
rnd = fastRand(rnd)
return level
One line the pseudocode doesn't show is how rnd is seeded, and it matters more than it looks. The O(log(n)) guarantee is probabilistic, so it rests on whoever controls the keys not knowing the coin flips - and an LCG's state is exactly its last output, so two observed levels recover the whole sequence. Seed it per process from something non-guessable (std::random_device, getrandom(2)), never from a constant.
See the real C++ random level definition in util.h
5.2Insert
General idea:
update[] array - the predecessors of inserting positionpseudocode
insert(key, value):
update[0..MAX_LEVEL-1] = header // never leave a predecessor unset
x = header
for i = level down to 0:
while x.next[i] != null and x.next[i].key < key:
x = x.next[i]
update[i] = x // once per level, AFTER the while
x = x.next[0]
if x != null and x.key == key: x.value = value; return
lvl = randomLevel() // top lane index of the new node
if lvl > level:
for i = level+1 to lvl: update[i] = header
level = lvl
newNode = Node(key, value, lvl) // next[] has lvl + 1 lanes
for i = 0 to lvl: // inclusive - lane lvl is a real lane
newNode.next[i] = update[i].next[i]
update[i].next[i] = newNode
Another line the pseudocode doesn't show is that for i = level down to 0 cannot be written that way once Level is unsigned: level >= 0 is always true, and the decrement past 0 wraps to 255 rather than ending the loop.
See the real C++ SkipList insert definition in skip_list_impl.h. The update[] walk itself is factored out into descend(), since delete needs the identical loop - one copy, so the two operations cannot drift apart in the one place a skip list is easiest to get wrong.
5.3Delete
Perform a loop like Inserting and delete the pointer after updating the pointers array:
pseudocode
delete(key):
build update[] exactly as in insert
x = x.next[0]
if x == null or x.key != key: return false
top = min(x.level, level)
for i = 0 to top:
if update[i].next[i] != x: break
update[i].next[i] = x.next[i]
free(x)
while level > 0 and header.next[level] == null: level -= 1
return true
That free is safe under a single writer with no concurrent readers, and the real C++ now does precisely that - one Node::destroy after the unlink loop, which runs the destructor and hands the block back. A lock-free skip list has to defer reclamation (hazard pointers, epoch-based reclamation, RCU) rather than freeing inline, because a reader may still be sitting on x while you unlink it.
See the real C++ SkipList delete definition in skip_list_impl.h
5.4Search
Walk through an example trace step by step in the GIF above
pseudocode
x = header
for i = level down to 0:
while x.next[i] != null and x.next[i].key < key:
x = x.next[i]
x = x.next[0]
if x != null and x.key == key: return x.value
return NOT_FOUND
See the real C++ SkipList search definition in skip_list_impl.h
The descent above is lowerBound - the first element not ordered before the value - and find is that plus a single check: the candidate is the value exactly when the value is not ordered before it either, so a membership test reads find(v) != end(). And the walk is free: lane 0 is still a plain sorted linked list, so an iterator is a node pointer and ++ is link(0).
06Complexity analysis
| Operations | Average | Worst case |
|---|---|---|
| Search | O(log(n)) | O(n) |
| Insert | O(log(n)) | O(n) |
| Delete | O(log(n)) | O(n) |
| Space | O(n) (expected) | O(n x MAX_LEVEL) |
Why O(log(n))?
Why O(n) in worst case?