Not technically a data structure, but Reservoir Sampling is an interesting probabilistic sampling technique used to choose a random sample from a population of unknown size N in a single pass, so useful for a data structure that does not fit in memory.
https://en.wikipedia.org/wiki/Reservoir_sampling