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. [0] http://www.andrew.cmu.edu/course/15-749/READINGS/required/cas/tridgell96.pdf [1] http://en.wikipedia.org/wiki/Bloom_filter
