A storage device includes a controller and nonvolatile memories. The controller receives write commands having virtual stream identifiers (IDs), receives discard commands having the virtual stream IDs, and determines a lifetime of write data to which each of the virtual stream IDs is assigned. The nonvolatile memories are accessed by the controller depending on physical stream IDs. The controller maps the virtual stream IDs and the physical stream IDs based on the lifetime of the write data.