This isn't a data structure technically but I find it clever: ZFS' space maps. It keeps track of which space is allocated by logging every allocation and deall

This isn't a data structure technically but I find it clever: ZFS' space maps. It keeps track of which space is allocated by logging every allocation and deallocation. When initializing an allocator, which can be implemented in any way, this log is replayed. If the map becomes too big it is rewritten so it is equivalent to the old map but with no redundant entries.