You mostly ask about data structures, but I thought I'd share one of my
favorite algorithms. The core rsync algorithm as described here[0] is quite
simple and brilliant.
Another interesting data structure is a Bloom filter[1].
I forgot to mention previously, that rb/AVL trees are also used for implementing
a virtual memory subsystem.