Skiplist

4752 2018-10-09 12:39

A skip-list is essentially a linked list that allows you to binary search on it. The way it accomplishes this is by adding extra nodes that will enable you to ‘skip’ sections of the linked-list. Given a random coin toss to create the extra nodes, the skip list should have O(logn) searches, inserts and deletes.

Usecases

  • LevelDB MemTable
  • Redis SortedSet
  • Lucene inverted index

如果这篇文章对你有帮助

在 Github 上 Follow 我 :)

下载 硅谷io App

关注互联网创业,用移动 App ,随时随地收藏和复习好文章