Skip to content
Range Queries & Iteration
step 1/5

Reading — step 1 of 5

Read

~1 min readDelete & 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

Discussion

Ask a question, share an insight, or help someone who’s stuck.

Sign in to post a comment or reply.

Loading…