Skip list
Probabilistic data structure — a sorted linked list with "expresses" at higher levels that let you skip past elements. O(log n) expected time.
William Pugh (1989) as a simpler alternative to balanced trees. Each node has a random number of "up-pointers" (classic p=0.5 per level). Lookup: start at the top, jump right as far as you can, drop down, repeat.
Powers Redis sorted sets (ZSET), the LevelDB/RocksDB memtable, Lucene posting lists. Win over balanced trees: easier lock-free implementation, better cache locality. Loses: guaranteed worst-case (can be O(n) on unlucky runs).