3.13.7. SkipList

Skiplists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees. Skiplists are more amenable to concurrent access/modification. The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked.

SkipList is widely used in LevelDB, Redis and Lucence. I fixed a bug in Redis’s SkipList implementation and improved the performance by 10%.

• Problem Statement

Figure 3.13.3 Forward linked list with O(N) for search, insert, and delete

• Intuition

Figure 3.13.4 Idea of skiplist by adding more layers but skipping some nodes

It is easy to understand the idea behind skiplist.

• Search with O(LogN)

Figure 3.13.5 Search node 37 in skiplist

• Insert with O(LogN)

Figure 3.13.6 Insert 9 and 30 into the skiplist