Splay tree

B-tree

Probabilistic data structures

Aho-Corasick

Cache-oblivious algorithms