スキップリスト
確率的データ構造。上の層に「急行」を持つ、整列済みの連結リストで、要素を飛ばして進める。期待計算量はO(log n)。
William Pughが1989年に、平衡木より単純な代替として考案した。各ノードはランダムな数の上向きポインタを持つ（典型的には1層あたりp=0.5）。探索は最上層から始め、行けるところまで右へ進み、1層下りて繰り返す。
Redisのソート済みセット（ZSET）、LevelDB/RocksDBのmemtable、Luceneのポスティングリストなどを支えている。平衡木に勝る点は、ロックフリー実装が容易なことと、キャッシュ局所性が良いこと。劣る点は、最悪計算量が保証されないこと（運が悪いとO(n)になりうる）。