Database / RocksDB Basics Interview Questions
What is a Skip List?
A Skip List is a probabilistic data structure that maintains sorted data with multiple layers of "express lane" links, letting it support fast search, insertion, and deletion without the complexity of a balanced tree.
- The bottom layer contains every element in sorted order, like a regular linked list
- Higher layers contain progressively fewer elements, acting as shortcuts that let a search skip over large portions of the list
- Achieves roughly logarithmic-time operations on average, comparable to a balanced tree, but with a notably simpler implementation
This is the data structure RocksDB's default MemTable implementation is built on, chosen for its efficient ordered access combined with straightforward concurrent-access properties.
What do higher layers of a Skip List act as?
What time complexity does a Skip List achieve on average?
More Related questions...
