1. A method of operating a storage device that includes an erase before write memory device and a controller controlling the erase before write memory device, the method comprising: maintaining a data structure, in the controller, that associates logical addresses received from an external device with physical addresses for units of memory allocation in the erase before write memory device, each of the units of memory allocation corresponding to a read/write operation unit of the erase before write memory device, and that includes indications of whether each data stored in the units of memory allocation corresponding to the physical addresses is invalid data deleted by an operating system driven on the external device; receiving a file delete command including a logical address invalidated from the operating system, the logical address being assigned to a physical address corresponding to at least one unit of memory allocation; and identifying the at least one unit of memory allocation in the erase before write memory as containing invalid data by updating the data structure in the controller, wherein the read/write operation unit and each unit of memory allocation is a page, and the data structure associates logical addresses with physical addresses by the unit of the page.