Step 1 of 5 · Reading · ~1 min
Read
Delete & Iterate
Range Queries & Iteration
The bottom level is just a sorted linked list. Range queries walk it linearly:
python
Skip list range queries are O(log n + k) — fast prefix walk + linear emission. Same as B-tree.
Iteration is just walking level 0:
python
Skip lists give you ORDERED iteration for free. Hash maps don't (without sorting).
Used heavily by:
- Redis ZRANGE, ZRANGEBYSCORE
- LevelDB iteration
- Cassandra range queries
Up nextConcurrent Skip ListsProduction Use
Discussion
Ask a question, share an insight, or help someone who’s stuck.
Sign in to post a comment or reply.
Loading…