Skip List

Definitions

1. A probabilistic data structure that maintains a sorted list with multiple levels of linked list shortcuts, enabling O(log n) search, insert, and delete. Simpler to implement than balanced trees while offering similar performance. Used by Redis for sorted sets and LevelDB/RocksDB for in-memory indexing.

   In plain English: A layered linked list with express lanes that let you skip ahead, making searches as fast as a balanced tree but simpler to build.

   Example: "Redis sorted sets use skip lists internally — that's why ZRANGEBYSCORE is O(log n + m), same complexity as a balanced tree."

Related Terms

• Array
• Binary Tree
• Cell Array
• Collections
• Record
• Bloom Filter
• B+ Tree
• LSM Tree