# 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

Intuition

It is easy to understand the idea behind skiplist.

Search with O(LogN)

Insert with O(LogN)