Skip list
Estrutura de dados probabilística — uma lista encadeada ordenada com "expressos" nos níveis superiores que permitem pular elementos. Tempo esperado O(log n).
Criada por William Pugh em 1989 como alternativa mais simples às árvores balanceadas. Cada nó tem um número aleatório de "ponteiros para cima" (o clássico é p=0,5 por nível). Na busca: comece no topo, ande para a direita o quanto puder, desça um nível e repita.
Está por trás dos sorted sets do Redis (ZSET), da memtable do LevelDB/RocksDB e das posting lists do Lucene. Vantagens sobre árvores balanceadas: implementação lock-free mais fácil e melhor localidade de cache. Desvantagem: não há garantia de pior caso (pode chegar a O(n) numa sequência azarada).