Skiplist

Definitions

1. A probabilistic data structure that maintains multiple layers of sorted linked lists, where each higher layer acts as an express lane by skipping over elements, providing O(log n) average-time search, insertion, and deletion — serving as a simpler-to-implement alternative to balanced binary search trees. Used in Redis sorted sets and LevelDB/RocksDB memtables.

   In plain English: A clever layered list where higher layers let you jump ahead quickly, like an express elevator that skips floors to find things faster.

   Example: "Redis uses a skiplist under the hood for sorted sets, which is why ZRANGEBYSCORE is logarithmic."

Related Terms

• Hash Map
• Hash Ring
• Hash Set
• Hashing Algorithm
• Priority Queue
• Radix Tree
• Search Tree
• Segment Tree
• Union Find