A storage device includes a memory device, and a memory controller configured to receive data and a log related to a property of the data from an external host, allocate a super block in which the data in the memory device is to be stored and a physical zone in the super block based on the log of the data, and store information for the log of the data stored for each physical zone and a time point at which a physical zone of a full state in which an empty area does not exist is switched to the full state. The memory controller controls the memory device to perform garbage collection according to the number of physical zones of an empty state, and selects a victim physical zone based on the information for the log of the data and a full state switch time point.