What are the lesser known but useful data structures?

It really annoys me that questions like this aren't welcome on Stack Overflow anymore. This is a great example of a question which doesn't have "one right answer" but is still constructive and relevant.