Skip List
· One min read
A skip list is essentially a linked list that allows for binary search. It achieves this by adding extra nodes that enable you to "skip" parts of the linked list. Given a random number generator to create these extra nodes, a skip list has O(log n) complexity for search, insert, and delete operations.
Use Cases
- LevelDB MemTable
- Redis Sorted Set
- Lucene Inverted Index
![[object Object]](https://tp-misc.b-cdn.net/tianpan-avatar.jpg){kind=avatar}