The present technology relates to an electronic device. A storage device includes a memory device including pages, a buffer memory configured to store address mapping information including a mapping relationship between logical addresses provided from a host and physical addresses corresponding to the pages, first trim bitmap information including trim information of first logical address groups each including a first number of logical addresses having at least two of the logical addresses, and second trim bitmap information including trim information of second logical address groups each including a second number of logical addresses greater than the first number of the logical addresses, and a memory controller configured to change, based on a number of trim-requested logical addresses from the host, map states of the trim-requested logical addresses in one of the address mapping information, the first trim bitmap information, and the second trim bitmap information.