Skip to content

Latest commit

 

History

History
19 lines (16 loc) · 876 Bytes

69-skiplist.md

File metadata and controls

19 lines (16 loc) · 876 Bytes
Raw
slug id title date comments tags description references
69-skiplist
69-skiplist
Skiplist
2018-10-09 12:39
true
system design
data structures
A skip-list is essentially a linked list that allows you to do a binary search on. The way it accomplishes this is by adding extra nodes that will enable you to ‘skip’ sections of the linked-list. There are LevelDB MemTable, Redis SortedSet and Lucene inverted index using this.

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