← recall

skip list term

sorted linked-list with multi-level shortcuts

Probabilistic alternative to balanced trees. Logarithmic operations. Used by Redis sorted sets, RocksDB memtable.

topics: data-structures, databases

references:

• Wikipedia — Skip list