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 <https://github.com/redis/redis/pull/5539>`_ in Redis's SkipList implementation and improved the performance by 10%.

- Problem Statement

.. figure:: skiplist_1.png
  :align: center
  :name: skiplist_1

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

- Intuition

.. figure:: skiplist_2.svg
  :align: center
  :name: skiplist_2

  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:: skiplist_3.svg
  :align: center
  :name: skiplist_3

  Search node 37 in skiplist

- Insert with O(LogN)

.. figure:: skiplist_4.svg
  :align: center
  :name: skiplist_4

  Insert 9 and 30 into the skiplist